product of array except self

← 🏠

O(N) space
O(N) time

 1from itertools import accumulate
 2from operator import mul
 3
 4def 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
 9print(productExceptSelf([1, 2, 3, 4]))
10
11productExceptSelf([1,2,3,4])

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

 1def 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
11print(productExceptSelf([1, 2, 3, 4]))