# Product of Array Except Self

## # Solution

All solutions below have complexities of linear time.

### # Prefix & Suffix Products

??? product in

#### # Linear Space

• `prefix_prod[i]`: products from `nums[0]` to `nums[i-1]`
• `suffix_prod[i]`: products from `nums[n-1]` to `nums[i+1]`

So the product except `nums[i]` is `prefix_prod[i-1]*suffix_prod[i+1]`.

``````def productExceptSelf(self, nums: List[int]) -> List[int]:
n = len(nums)
if n==0:
return []

# calculate prefix product
prefix_prod = [0]*n
prefix_prod[0] = nums[0]
for i in range(1,n):
prefix_prod[i] = prefix_prod[i-1]*nums[i]

# calculate prefix product
suffix_prod = [0]*n
suffix_prod[n-1] = nums[n-1]
for i in reversed(range(n-1)):
suffix_prod[i] = suffix_prod[i+1]*nums[i]

# calculate res
res = [0]*n
res[0] = suffix_prod[1]
res[n-1] = prefix_prod[n-2]
for i in range(1,n-1):
res[i] = prefix_prod[i-1]*suffix_prod[i+1]

return res
``````

### # Constant Space

We can just accumulate `prefix_prod` and `suffix_prod` as a number rather than an array and update `res` accordingly.

This way we have 1 less for loop and constant space.

``````def productExceptSelf(self, nums: List[int]) -> List[int]:
n = len(nums)
if n==0:
return []
res = [1]*n
# calculate prefix product from front to back
prefix_prod = 1
for i in range(n):
res[i] = prefix_prod # use *= instead?
prefix_prod *= nums[i]

# calculate suffix product from back to front
suffix_prod = 1
for i in reversed(range(n)):
res[i] *= suffix_prod
suffix_prod *= nums[i]

return res
``````
Last Updated: 7/19/2020, 3:45:14 PM