Product of array except self

Two passes. The first fills each cell with the product of everything to its left; the second walks backwards multiplying by a running product of everything to the right. O(n) time, no division, and the output array is the only extra memory.

Lists & arraysCoding problemMedium

Step through it

What to watch

  • After the first pass each cell knows only about its left.
  • The second pass folds in the right side without a second array.
  • No element is ever divided — zeros need no special handling.

Say this out loud

"Prefix products left to right, then a running suffix product right to left, multiplied into the same array. O(n) time, O(1) extra space beyond the output - and no division, so zeros are not a special case."

Overview

For each position, return the product of all other values without division. A prefix pass and a suffix pass combine the product on each side; zero values work naturally without a special division case.

In this guide
  1. Run it: Product of array except self in code
  2. Prefix and suffix products
  3. Tracing it
  4. Why not just divide
  5. The decomposition
  6. The pattern to spot
  7. Zeros, which are the interesting case
  8. Edge cases
  9. The variants
  10. Sources and next steps

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.

1Python
Output
2Python
Output

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.

3Python
Output

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:

iprefix beforeout[i]prefix after
0111
1112
2226
36624

out = [1, 1, 2, 6] — each entry is the product of all of it to its left.

Backward pass — multiplying in suffix products:

isuffix beforeout[i] beforeout[i] aftersuffix after
31664
242812
11211224
02412424

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

CaseResult
[1, 2][2, 1]
[5][1] — the empty product
[][]
Contains one zeroOnly that position is non-zero
Contains several zerosAll zeros
Negative numbersHandled — signs multiply normally
Large valuesPython 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.

Sources and next steps

How the code works

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.

How the code works

  1. result[i] = running (before the update)Assign first, then fold in values[i]. Doing it the other way round includes the element itself, which is precisely what the question excludes.
  2. the second loop reuses `result`The output array carries the left products into the right pass, so no second array is needed. That is what takes the extra space from O(n) to O(1).
  3. running = 1The identity for multiplication, so the first prefix and last suffix contribute nothing. A sum-based variant would start at 0 — the usual off-by-identity bug.
  4. by_divisionKept to be broken. One zero and the division fails; two zeros and even a special case has to know how many there were.

Change one thing

  • Fix the division version by counting zeros first. It works, and compare how much longer it is than the two-pass one.
  • Change the operation to addition — sum of everything except self. The identity becomes 0 and the structure is unchanged.

Where this runs

Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.

Check yourself

0 of 3

Answer without scrolling back up.

  1. Why is division ruled out?

  2. The extra space beyond the output array is:

  3. Why is the running product initialised to 1?

Cheat sheet

Product of array except self

Build prefix and suffix products in two passes to get the product of every other element, with no division and O(1) extra space.

INTERVIEW · vizlearn.in/interview/product-of-array-except-self.html

About the author

Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.

Teaching a course with this? Individual teachers can use it freely; for a whole department or programme, see institutional licences.