Question:

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, a1a2

a3]a4, a4, 1]

[a2a3a4, a3

**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 = [1] * size
ary_right = [1] * 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.