## 238. Product of Array Except Self

Given an array `nums`of n integers where n> 1, return an array `output`such that `output[i]`is equal to the product of all the elements of `nums`except `nums[i]`.

Example:

``````Input: [1,2,3,4]
Output: [24,12,8,6]
``````

Note: Please solve it without division and in O(n).

Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)

Code: with extra space:

``````class Solution(object):
def productExceptSelf(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
m = collections.defaultdict(list)
p = 1
for i, num in enumerate(nums):
m[i] = p
p *= num

p = 1

for i, num in reversed(list(enumerate(nums))):
m[i] *= p
p *= num

return [m[k] for k in sorted(m.keys())]
``````

Code: without extra space:

``````class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int res [] = new int [n];
int p = 1;

// multiply left
for(int i = 0; i < n; i++){
res[i] = p;
p *= nums[i];
}

// multiply right
p = 1;
for(int i = n - 1; i >=0 ; i--){
res[i]*= p;
p *= nums[i];
}

return res;
}
}
``````

Code: actually index is the key: so we do not need the extra dictionary

``````class Solution(object):
def productExceptSelf(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
# m = collections.defaultdict(list)
res = [0] * len(nums)
p = 1
# left
for i, num in enumerate(nums):
res[i] = p
p *= num

p = 1

for i, num in reversed(list(enumerate(nums))): # i is also reversed
res[i] *= p
p *= num

return res
``````