product of array except self

🏠

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 def productExceptSelf(nums):
 2     ans = [1] * len(nums)
 3     left, right = 1, 1
 4     for i in range(len(nums)):
 5         ans[i] *= left
 6         ans[~i] *= right
 7         left *= nums[i]
 8         right *= nums[~i]
 9     return ans
10 
11 print(productExceptSelf([1, 2, 3, 4]))