Run it
The two-pass version with both intermediate states printed, checked against the division shortcut — which is given arrays containing one zero and two zeros so you can watch it fail.
Prefix and suffix products
Every element's answer is everything before it, times everything after it. Compute those two directions in separate passes.
O(n) time, and O(1) extra space if the output array is not counted — which is the usual convention, and worth stating.
The ordering inside each loop is what makes it work: out[i] is assigned before prefix is updated with nums[i], so it never includes the element itself. Reversing those two lines is the standard bug.
Tracing it
[1, 2, 3, 4]:
Forward pass — prefix products:
| i | prefix before | out[i] | prefix after |
|---|
| 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 2 |
| 2 | 2 | 2 | 6 |
| 3 | 6 | 6 | 24 |
out = [1, 1, 2, 6] — each entry is the product of everything to its left.
Backward pass — multiplying in suffix products:
| i | suffix before | out[i] before | out[i] after | suffix after |
|---|
| 3 | 1 | 6 | 6 | 4 |
| 2 | 4 | 2 | 8 | 12 |
| 1 | 12 | 1 | 12 | 24 |
| 0 | 24 | 1 | 24 | 24 |
out = [24, 12, 8, 6]. Correct.
The two-table trace is worth doing on paper in an interview — the algorithm is short and the index handling is exactly where errors occur.
Why not just divide
Multiply everything, then divide by each element. It is O(n), it is the first thing everyone says, and the question explicitly forbids it — because it breaks on zero. One zero makes every other answer a division by zero; two zeros make every answer zero.
You can special-case the zero count, and it works. Say that, then give the prefix/suffix answer, because the point of the question is the decomposition rather than the arithmetic.
The decomposition
The product of everything except element i is (everything left of i) × (everything right of i). Both of those are cumulative products, and each can be built in one pass.
The trick that gets you to O(1) extra space is to store the left products directly in the output array, then walk backwards carrying the right product in a single variable and multiplying it in. No second array is ever allocated.
The pattern to recognise
"Something about everything except me" is almost always prefix and suffix aggregates. The same shape solves trapping rain water (max to the left and right of each bar), candy distribution, and the maximum-product subarray.
Note the convention: the leftmost prefix and the rightmost suffix are both 1, the identity for multiplication. For a sum-based variant they would be 0. Getting the identity wrong is the usual bug.
Zeros, which are the interesting case
The prefix-suffix solution handles zeros with no special casing at all, which is one of its attractions. It is worth verifying rather than asserting:
One zero, [1, 0, 3]: the answer is [0, 3, 0]. The zero position gets the product of its neighbours; every other position includes the zero and is therefore zero. The algorithm produces this naturally.
Two zeros, [0, 2, 0]: every position sees at least one zero, so the answer is [0, 0, 0].
Compare with the division approach, which needs explicit counting: no zeros means divide normally; one zero means only that position is non-zero; two or more means everything is zero. Three branches, and each is a chance to get it wrong.
That contrast is worth stating: the prefix-suffix method is not merely allowed under the constraint, it is genuinely simpler.
Edge cases
| Case | Result |
|---|
[1, 2] | [2, 1] |
[5] | [1] — the empty product |
[] | [] |
| Contains one zero | Only that position is non-zero |
| Contains several zeros | All zeros |
| Negative numbers | Handled — signs multiply normally |
| Large values | Python integers are unbounded; other languages overflow |
The single-element case returning [1] is the empty-product convention, and it is worth confirming with the interviewer rather than assuming.
The overflow row matters in languages with fixed-width integers: the product of many values overflows silently. Python has no such limit, and mentioning that the problem is harder in C or Java demonstrates awareness.
The variants
Two-pass with explicit arrays. Build prefix[] and suffix[] separately, then multiply. O(n) space, easier to explain, and a reasonable first version before optimising to O(1).
Sum of array except self. Trivially the total minus each element — subtraction has no zero problem, which is exactly why the product version is the interview question.
Product of array except self, division allowed. Count zeros and branch, as above. Worth writing out if asked, to show the case analysis is understood.
Maximum product subarray. A different problem, and a common companion question: track both the running maximum and minimum, because multiplying by a negative swaps them.
Product of every window of size k. Prefix products plus division, or a sliding-window approach handling zeros by tracking the last zero's position.
What it is testing
Do you find the prefix-suffix decomposition? "Everything before, times everything after" is the insight, and it is a genuinely non-obvious reframing.
Do you achieve O(1) extra space? Reusing the output array for the prefix pass and multiplying the suffix in during the second is the expected refinement.
Do you get the index ordering right? Assigning before updating the accumulator is the one place the code breaks.
Do you handle zeros without special cases? And can you explain why no special case is needed?
Do you notice the division approach's zero problem even though division is banned anyway?
The transferable technique is precomputed prefix aggregates. Prefix sums answer range-sum queries in O(1); prefix products, prefix maxima and prefix counts all follow the same shape. Recognising when a problem wants "everything before this point" is worth more than this specific solution.
Recap in one screen
- Each answer is the product of everything to the left times everything to the right.
- Two passes: fill the output with prefix products, then multiply suffix products in going backwards.
- O(n) time and O(1) extra space beyond the output array.
- Assign
out[i] before folding nums[i] into the accumulator, or the element includes itself. - Zeros need no special handling, which is why this beats the division approach even when division is allowed.