https://leetcode.com/problems/product-of-array-except-self/

Prefix product * suffix product

first pass, from left to right, for each index, store the product from left to index – 1

second pass, from right to left, for each index, multiply value with product from right to index + 1

Example:

``````init:
1, 1, 1, 1

given array
2, 3, 4, 5

expected result:
60, 40, 30, 24

after 1st pass, we get
1, 2, 6, 24 <- see the last index is the result, since it's product other than self is the product from left to second-to-last element

second pass:
res[3], do nothing, since there's no element to its right
res[2], multiply with array[3]
res[1], multiply with array[3] * array[2]
res[0], multiply with array[3] * array[2] * array[1]

so in the second pass, in the for loop, keep track of the product from last element to current
``````

Code in Python

``````class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:

res = [1] * len(nums)

for i in range(1, len(nums)):
res[i] = res[i-1] * nums[i-1]

tmp = 1
for i in range(len(nums) - 2, -1, -1):
tmp *= nums[i+1]
res[i] *= tmp

return res
``````

# Summary

Prefix and Suffix sum or product is a technique to learn

# Similar Problems

1658. Minimum Operations to Reduce X to Zero

437. Path Sum III