Run it: Product of array except self in code
The two-pass version prints both intermediate states and compares its results with the division shortcut on arrays containing one zero and two zeros. Those cases show why division needs special handling.
Prefix and suffix products
Every element's answer is all of it before it, times all of it 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 all of it 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 all of it, then divide by each element. It is O(n), it is the first thing everyone says. And the question by name 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 all of it except element i is (all of it left of i) × (all of it 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 right 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 spot
"Something about all of it 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 product. 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. This 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 so zero. The algorithm gives 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 all of it 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 truly 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 shows awareness.
The variants
Two-pass with explicit arrays. Build prefix[] and suffix[] apart, then multiply. O(n) space, easier to explain, and a fair first version before optimising to O(1).
Sum of array except self. Trivially the total minus each element. Subtraction has no zero problem. This 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.