Product of Array Except Self
Problem statement
Statement
Given an integer array nums, return an array answer where answer[i] is the product of every element of nums except nums[i]. You must run in O(n) time and you may not use division.
Examples
nums = [1, 2, 3, 4]
-> [24, 12, 8, 6] (24 = 2*3*4, 12 = 1*3*4, and so on)
nums = [-1, 1, 0, -3, 3]
-> [0, 0, 9, 0, 0] (only the slot holding the zero survives)
nums = [0, 0]
-> [0, 0] (two zeros kill every position)
nums = [2, 3]
-> [3, 2]Constraints
2 <= len(nums) <= 10^5-30 <= nums[i] <= 30- Every prefix and suffix product fits in a 32-bit signed integer, so you never need big integers.
- The output array is conventionally excluded from the space bound.
What this problem is really testing
The no-division rule is not arbitrary difficulty for its own sake. Division looks like a one-liner (compute the total product, divide by each element) and it is wrong twice over. It breaks on any zero, and with two zeros it cannot be patched by special-casing, because every output is zero and the surviving total is meaningless. Forbidding division forces you to find the structure that was hiding behind the arithmetic shortcut.
That structure is a split. The product of everything except nums[i] is the product of everything to its left times the product of everything to its right. Once stated that way, the problem is no longer about products at all: it is about computing, for every position, an aggregate of the prefix before it and the suffix after it. The same skeleton computes running sums, running maxima, running counts of any associative operation. Recognising the shape is worth more than the specific answer, and it is the shape explored in prefix sums in practice.
The elegant part is the memory. The obvious implementation builds a left array and a right array, then multiplies them pairwise, which is three arrays and O(n) auxiliary space. The trick is to notice that the two passes touch each index at different times, so the output array can hold the left products during the first pass and absorb the right products during the second, with a single scalar carrying the running suffix. Two passes, one array, one variable. That collapse from three arrays to one is precisely what the interviewer is waiting to see.
Hints
Hints
- Notice why division is banned rather than merely discouraged. Total product divided by
nums[i]fails the moment any element is zero, and with two zeros there is nothing to divide by and no patch that recovers the answer. The restriction is pointing you at the real structure. - Split the product at the index.
answer[i] = (product of nums[0..i-1]) * (product of nums[i+1..n-1]). Neither factor includesnums[i], which is the entire requirement. - Build the left factors in one forward pass. Carry a running product and write it into
answer[i]before multiplyingnums[i]into it. That ordering is what keeps the element itself out of its own cell. - Build the right factors in one backward pass. Carry a second running product from the end and multiply it into
answer[i], again writing before you fold the current element in. After both passes, every cell holds left times right. - Start both running products at 1, not at the first element. Index 0 has nothing to its left, and the product of an empty set is 1, the multiplicative identity. Seeding with
nums[0]shifts every value by one position and corrupts the whole array. - Collapse the suffix array into a scalar. The backward pass reads
answer[i], multiplies, and writes it back, so the suffix product only ever needs its current value. One integer replaces an entire array and takes the auxiliary space to O(1).
Solution and approaches
Solution: three approaches
Approach 1 - Nested loops: O(n^2) time, O(1) auxiliary space
The definition, written out. Correct, and quadratic.
def product_except_self_brute(nums):
n = len(nums)
answer = [1] * n
for i in range(n):
for j in range(n):
if i != j:
answer[i] *= nums[j]
return answerEach output element requires a full scan of the input, so the work is n outer iterations times n inner ones, which is Theta(n^2). At the constraint of 10^5 that is 10^10 multiplications, far past any time limit. It needs no cleverness and no extra memory, which makes it a useful reference implementation to differential-test the fast version against on random small inputs. It is also worth noticing what it wastes. Computing answer[0] multiplies nums[1] through nums[n-1], and computing answer[1] multiplies almost the same set again, differing in two positions. Nearly every multiplication is repeated across adjacent outputs, and that redundancy is exactly what the prefix and suffix decomposition eliminates. Spotting repeated subcomputation between neighbouring answers is the same instinct that produces prefix sums, running maxima and sliding windows, so it is worth articulating rather than jumping straight to the known trick.
Approach 2 - Prefix and suffix arrays: O(n) time, O(n) auxiliary space
The intermediate step. Materialise both halves, then combine.
def product_except_self_two_arrays(nums):
n = len(nums)
left, right = [1] * n, [1] * n
for i in range(1, n):
left[i] = left[i - 1] * nums[i - 1]
for i in range(n - 2, -1, -1):
right[i] = right[i + 1] * nums[i + 1]
return [left[i] * right[i] for i in range(n)]Why it is correct: left[i] is defined as the product of nums[0..i-1] and is built by extending the previous prefix with nums[i - 1], so each cell costs one multiplication. right[i] is the mirror image. Their product contains every element except nums[i] exactly once, because the two ranges are disjoint and together cover everything but index i. Three linear passes, so O(n) time, at the cost of two auxiliary arrays. Write this version first if the collapse is not yet obvious to you; it is much easier to verify by hand and it converts into approach 3 mechanically. The conversion is worth spelling out, because it is the same manoeuvre that turns most two-array dynamic programmes into one-array ones. Observe that the forward pass writes left[i] and nothing ever reads it again until the final combination, and that the backward pass reads right[i] exactly once at index i. A value written once and read once at a known moment does not need an array; it needs a variable. Apply that to right and it becomes the suffix scalar, and apply it to left and it merges into the output buffer.
Approach 3 - Two passes, one array, one scalar: O(n) time, O(1) auxiliary space
The expected answer. The output array does double duty.
def product_except_self(nums):
n = len(nums)
answer = [1] * n
prefix = 1
for i in range(n):
answer[i] = prefix # write before folding nums[i] in
prefix *= nums[i]
suffix = 1
for i in range(n - 1, -1, -1):
answer[i] *= suffix # answer[i] already holds the left product
suffix *= nums[i]
return answerWhy the write-then-multiply order is the whole algorithm: at the top of iteration i, prefix holds the product of nums[0..i-1] and has not yet seen nums[i]. Storing it first and folding the current element in afterwards is what guarantees nums[i] never contaminates its own cell. Swap the two lines and every entry is multiplied by itself, which on [1, 2, 3, 4] produces [1, 2, 6, 24], a sequence that looks structured enough to pass a casual eyeball check.
Why one scalar can replace the suffix array: the backward pass visits index i exactly once and, at that moment, needs only the product of everything strictly to the right of i. That value is fully determined by what the pass has already consumed, so it can live in a single variable that is updated as the pass moves left. Nothing ever needs to look back at an earlier suffix. The same collapse applies to any prefix or suffix aggregate consumed in a single sweep, which is why this pattern shows up far beyond this problem.
Why zeros need no special case: a zero in the input simply makes every prefix beyond it and every suffix before it zero, and those zeros propagate into exactly the cells that should be zero. With one zero at index z, only answer[z] is the product of the non-zero elements, because its left factor stops before the zero and its right factor starts after it. With two or more zeros, every cell has a zero on one side or the other and the whole output is zero. The arithmetic handles all three cases with no branches, which is the strongest argument against the division approach.
Why the space claim needs a qualifier: the algorithm allocates one array of size n, which is the output. The convention in this problem is to exclude the required output from the space bound, so the honest statement is "O(1) auxiliary space beyond the output". Claiming a flat O(1) without that qualifier invites the follow-up about where the answer is being stored.
Worked trace on [1, 2, 3, 4]
| i | prefix before write | answer after pass 1 | suffix before write | answer after pass 2 |
|---|---|---|---|---|
| 0 | 1 | 1 | 24 | 24 |
| 1 | 1 | 1 | 12 | 12 |
| 2 | 2 | 2 | 4 | 8 |
| 3 | 6 | 6 | 1 | 6 |
Complexity comparison
| Approach | Time | Auxiliary space | Handles zeros | Notes |
|---|---|---|---|---|
| Total product and divide | O(n) | O(1) | No | Forbidden, and wrong on zeros |
| Nested loops | O(n^2) | O(1) | Yes | Reference only |
| Prefix and suffix arrays | O(n) | O(n) | Yes | Easiest to verify by hand |
| Two passes, one scalar | O(n) | O(1) | Yes | Expected answer |
Edge cases to verify
- Two elements:
[2, 3]gives[3, 2]. The minimum legal input, and it catches seed errors on either running product. - Exactly one zero:
[-1, 1, 0, -3, 3]gives[0, 0, 9, 0, 0]. Only the zero's own slot is non-zero. - Two zeros:
[0, 0]gives[0, 0]. This is the input that no division-plus-special-case solution survives. - Negative values:
[-1, -2, -3]gives[6, 3, 2]. Sign handling is automatic; no absolute values anywhere. - All ones:
[1, 1, 1]gives[1, 1, 1], confirming the empty-product seed of 1 is right.
Common mistakes
Where beginners go wrong
- Reaching for division anyway. Beyond being explicitly banned, it breaks on zeros: one zero makes every quotient undefined except at the zero's own index, and two zeros make the total product zero so there is nothing left to recover. Candidates who special-case "count the zeros" end up with three branches where the prefix and suffix method has none.
- Multiplying before writing. The single line that decides correctness.
prefix *= nums[i]must come afteranswer[i] = prefix, otherwise each cell includes its own element. On[1, 2, 3, 4]the wrong order yields[1, 2, 6, 24], which is a real sequence and passes a glance. - Seeding the running product with
nums[0]. Index 0 has nothing to its left, and the empty product is 1. Starting withnums[0]shifts every left factor one position and produces an array that is wrong everywhere but sometimes right at one end. - Keeping a full suffix array. Correct, and it leaves O(n) auxiliary space on the table. The backward pass only ever needs the current suffix value, so one integer suffices. If you write the two-array version first, say out loud that you will now collapse it.
- Mutating
numsto save space. Overwriting the input destroys values the second pass still needs, and it violates the caller's expectations. The output array plus one scalar is already optimal; there is nothing to gain. - Claiming O(1) space without the qualifier. The output array is O(n) memory. The convention excludes it, but say "O(1) auxiliary beyond the output" rather than inviting a follow-up you then have to walk back.
Interview follow-ups to expect
- "Now division is allowed. What changes?" Count the zeros. Zero of them means total divided by each element. Exactly one means every cell is 0 except the zero's own, which gets the product of the rest. Two or more means the whole array is zero. Three branches instead of none, which is a good moment to observe that the banned operation was making the code worse, not just slower to reason about.
- "Return sums except self instead of products." Total sum minus
nums[i], in one pass, because subtraction has an inverse that is always defined. The contrast explains exactly why products need the two-pass structure: there is no safe multiplicative inverse for zero. - "Do it for a 2D grid, excluding the whole row and column." Same decomposition in two dimensions: precompute row aggregates and column aggregates, then combine. O(rows * cols) time with O(rows + cols) extra memory.
- "What if the products overflow?" The constraints promise 32-bit safety, but drop that and you need arbitrary precision, modular arithmetic under a prime, or logarithms if approximation is acceptable. Working in log space converts products to sums and loses exactness, which is usually the wrong trade for an interview and the right one in numerical code.
- "Support updates: change one element, then re-query." A segment tree over products answers any range product in O(log n) and supports point updates in O(log n), which beats recomputing the prefix arrays from scratch at O(n) per update.
- "Can it be done in one pass?" Not with this decomposition, since
answer[0]depends on the last element, which a single forward pass has not seen yet. Being able to say why a one-pass version cannot exist is a better answer than trying to construct one.
Related reading
- Prefix Sums in Practice: the general pattern, of which prefix products are one instance.
- Arrays and Sequences: the module this belongs to, including why reusing the output buffer is the standard way to drop an auxiliary array.
- Subarray Sum Equals K: prefix aggregates again, this time paired with a hash map to answer a range question in one pass.