Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to
the product of all the elements of nums except nums[i].
Solve it without division and in O(n).
For example, given [1,2,3,4], return [24,12,8,6].
When getting this question, the first thing comes to my mind is to use the reduce function, which can help you get the product of a number of numbers. So the code would be:
class Solution(object): # Solution 1 # not passing the performance requirements def productExceptSelf1(self, nums): """ :type nums: List[int] :rtype: List[int] """ aryRes =  import copy for e in nums: tmpNums= copy.deepcopy(nuts) # line 12 tmpNums.remove(e) Res.append(reduce(lambda x,y:x*y, tmpNums)) return aryRes
From the code you can see, line 12 I copy the original list to a new list, by doing this I can remove the corresponding element one by one and use the reduce function to get the product of rest numbers. For example, with given an array [1,2,3,4], you can get the product of [2,3,4] by using:
reduce(lambda x,y:x*y, [2,3,4])
However the submission did not pass the performance test, the running time: Total time: 0.000423 s (avg). So let.s move on on this journey 🙂
So commonly, if we want to boost our program, we can use some variables to store intermedia data. for example, if we have nums [a1, a2, a3, a4]. for each pass, we can calculate the product of all left numbers as well as the products from all right numbers. So the version 2 solution can be:
def productExceptSelf2(self, nums): """ :type nums: List[int] :rtype: List[int] """ aryRes =  for index in range(len(nums)): #print nums[:index], nums[index+1:] product_left = reduce(lambda x,y:x*y,nums[:index]) if(nums[:index]!=) else 1 product_right = reduce(lambda x,y:x*y,nums[index+1:]) if(nums[index+1:]!=) else 1 aryRes.append(product_left*product_right) return aryRes
This time, it is a little bit faster. After using the kernprof (which is an python performance profiling tool, https://github.com/rkern/line_profiler) , the cost time is roughly Total time: 0.000114 s (avg). So we may assume that most of the time is wasted on the reduce function. After checking online, there should be a much more efficient way of replacing reduce. Based on the solution 2, we know that we can use an intermediate variables to store intermediate results. With given nums=[a1, a2, a3, a4], and we want res= [a2a3a4, a1a3a4, a1a2a4, a2a3a4], we can think about using two arrays to multiple with each other.
[1, a1, a1a2, a1a2a3]
[a2a3a4, a3a4, a4, 1]
Aim to get:
[a2a3a4, a1a3a4, a1a2a4, a2a3a4]
So the first thing we can do is creating those two lists, and multiply them with position corresponding with each other.
def productExceptSelf3(self, nums): """ :type nums: List[int] :rtype: List[int] """ size = len(nums) ary_left =  * size ary_right =  * size ary_res = ` for i in range(size-1): ary_left[i+1]*= ary_left[i]*nums[i] for i in range(size-1, 0, -1): ary_right[i-1]*= ary_right[i]*nums[i] for i in range(size): ary_res.append(ary_left[i]*ary_right[i]) return ary_res
Total time: 3.3e-05 s.
Thanks for your time.