DSA Patterns (Multi-Lang)•Part 2: Arrays, Strings & Hash Maps (6 - 18)
Product of Array Except Self.
In Simple Words: Do two passes without division: first compute running prefix products from left to right; then multiply by running suffix products from right to left.
- Time: $O(N)$ | Space: $O(1)$ auxiliary
Multi-Language SolutionsPython 3 • JavaScript • TypeScript • Java • C++
Switch tabs or choose Alldef productExceptSelf(nums: list[int]) -> list[int]:
n = len(nums)
res = [1] * n
prefix = 1
for i in range(n):
res[i] = prefix
prefix *= nums[i]
postfix = 1
for i in range(n - 1, -1, -1):
res[i] *= postfix
postfix *= nums[i]
return res