vizlearn

Product of array except self

Interview QuestionsBy Updated

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.

Overview

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.

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."

Product of array except self

For each element, return the product of every other element - without using division.

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.

Run it in Python

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.

product_except_self.pyPython 3
Output
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
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.
INTERVIEW · vizlearn.in/interview/product-of-array-except-self.html
More in Interview
InterviewHow does a Python dict work?InterviewWhy must dictionary keys be hashable?InterviewCount things with a dictionaryInterviewWhat is the complexity of this code?
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.
About VizLearnGitHubLinkedInContact