Description
For each position, return the product of all other entries without division. Prefix and suffix products fit signed 32-bit integers.
Solution
def product_except_self(nums):
result = [1] * len(nums)
prefix = 1
for i, value in enumerate(nums):
result[i] = prefix
prefix *= value
suffix = 1
for i in range(len(nums)-1, -1, -1):
result[i] *= suffix
suffix *= nums[i]
return resultExamples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
[[2,3,4]]- Output
[12,8,6]
Each result multiplies the other two entries.
Example 2
- Input
[[0,2,3]]- Output
[6,0,0]
Only the position of the zero has a nonzero product.
Example 3
- Input
[[0,0,4]]- Output
[0,0,0]
Every excluded-position product still includes a zero.
Approach
Write prefix products into the output, then multiply by a rolling suffix product.
Time & space
O(n) time; O(1) auxiliary space excluding O(n) output. Here n is the input length.