**Solution**

**Product of Array Except Self** https://leetcode.com/problems/product-of-array-except-self/

**Solution using two arrays**

- First engineer a solution using two arrays.

```
class Solution(object):
def productExceptSelf(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
N = len(nums)
output1 = [1]*N
for i in xrange(1,N):
output1[i] = output1[i-1]*nums[i-1]
output2 = [1]*N
for i in xrange(N-2, -1, -1):
output2[i] = output2[i+1]*nums[i+1]
for i in xrange(N):
output1[i] = output1[i]*output2[i]
return output1
```

**Optimizing two array solution**

- Merge the last two for loops.

```
for i in xrange(N-2, -1, -1):
output2[i] = output2[i+1]*nums[i+1]
for i in xrange(N):
output1[i] = output1[i]*output2[i]
for i in xrange(N-2, -1, -1):
output2[i] = output2[i+1]*nums[i+1]
output1[i] = output1[i]*output2[i]
```

- Now we can remove output2 array and replace with the prev value

```
prev = 1
for i in range(N-2, -1, -1):
prev *= nums[i+1]
output1[i] *= prev
```

**Optimized Code**

```
class Solution1(object):
def productExceptSelf(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
N = len(nums)
output1 = [1]
for i in range(1,N):
output1.append(output1[-1]*nums[i-1])
prev = 1
for i in range(N-2, -1, -1):
prev *= nums[i+1]
output1[i] *= prev
return output1
```