Return an array where each element is the product of all other elements, without using division.
Make two passes: a left pass where each position accumulates the product of everything to its left, then a right pass (using a rolling variable) that multiplies in everything to its right. The two passes together give the complete product-of-all-others in O(n) time and O(1) extra space (excluding output).
How to think about it
Recognise the pattern
The signal is “product of all others” + “no division”. The no-division constraint rules out the naive “total product / current element” approach. What remains? Think about what goes into result[i]: everything to the left of i, and everything to the right of i. Those are two independent multiplications — two passes.
Build the approach step by step
With division (not allowed): multiply everything to get total, then result[i] = total / nums[i]. Breaks on zeros and is banned by the problem.
Two-pass prefix-product:
Pass 1 (left products): result[i] = product of all elements strictly to the left of i. Seed with 1 (nothing to the left of index 0).
nums: [1, 2, 3, 4]
left: [1, 1, 2, 6] (1, 1*1, 1*2, 1*2*3)Pass 2 (right products): scan right-to-left with a running variable right_prod (starts at 1). Multiply result[i] by right_prod, then update right_prod by multiplying in nums[i].
right: [24, 12, 4, 1] (4*3*2, 4*3, 4, 1)
result: [24, 12, 8, 6] (left * right per index)No extra array needed for the right pass — just a single accumulator variable.
Complexity
- Time — O(n): two linear passes.
- Space — O(1) extra: the output array
resultis required by the problem and does not count as extra space. The only extra variable isright_prod.