product of array except self

Go Back home

O(N) space
O(N) time

 1 from itertools import accumulate
 2 from operator import mul
 3 
 4 def productExceptSelf(nums):
 5     left_prod = [*accumulate([1]+nums[:-1], mul)]
 6     right_prod = [*reversed([*accumulate(reversed(nums[1:] + [1]), mul)])]
 7     return [*map(mul, left_prod, right_prod)]
 8 
 9 print(productExceptSelf([1, 2, 3, 4]))
10 
11 productExceptSelf([1,2,3,4])

Using the single bidirectional pass pattern results in O(1) space and O(N) time.

 1 from operator import mul
 2 
 3 def productExceptSelf(nums):
 4     ans = [1] * len(nums)
 5     left, right = 1, 1
 6     for i in range(len(nums)):
 7         ans[i] *= left
 8         ans[~i] *= right
 9         left *= nums[i]
10         right *= nums[~i]
11     return ans
12 
13 print(productExceptSelf([1, 2, 3, 4]))