Product of Array Except Self
For every position, multiply all the other numbers together, without using division.
- Prefix and suffix products
Before this, know: Arrays and indexes, Loops that count down as well as up
You get an array of numbers nums. Build a new array answer of the same
length where answer[i] is the product of every number in nums except
nums[i]. (The product is what you get by multiplying numbers together.)
Example: nums = [1, 2, 3, 4].
- 10
- 21
- 32
- 43
- 240
- 121
- 82
- 63
The rules that matter:
- You may not use division. This is the whole challenge (more on why below).
- It must run in O(n) time: a fixed number of passes over the array, no nested loops. (Big-O notation is a short way of saying how the work grows as the input grows; O(n) means “double the array, double the work”. See Big-O in 5 minutes.)
- Numbers can be negative or zero. Every product fits in a normal 32-bit integer.
- Follow-up: use only O(1) extra space (the
answerarray itself doesn’t count).
Our problem is the same with multiplication instead of counting. For any index i, “everything except me” splits into two parts: everything to my left and everything to my right.
- 10
- 21
- 32
- 43
- 10
- 21
- 32
- 43
A running product from the left is called a prefix product (“prefix” means “the beginning part”); a running product from the right is a suffix product (“the end part”).
Pause and think
Division is banned by the rules, but it’s also broken by zeros. The total of
[3, 0, 5] is 0, and dividing 0 by 0 for the middle slot is undefined. Yet the
right answer there is 3 × 5 = 15. The prefix/suffix idea never divides, so it
handles zeros naturally.
For each index i, walk the whole array and multiply every number except
nums[i].
Brute force: multiply everything else
nums = [1, 2, 3, 4]
- 10
- 21
- 32
- 43
- empty
- product
- 1
- multiplications
- 0
- Slot we're filling (i)
- Multiplying in (j)
- Skipped (j = i)
- Just written
j = i = 0: skip ourselves.
Which line is running?
function productExceptSelf(nums) { const answer = []; for (let i = 0; i < nums.length; i++) { let product = 1; for (let j = 0; j < nums.length; j++) {Running now: if (j !== i) product *= nums[j]; // skip ourselves } answer.push(product); } return answer;}Brute force
function productExceptSelf(nums) { const answer = []; for (let i = 0; i < nums.length; i++) { let product = 1; for (let j = 0; j < nums.length; j++) { if (j !== i) product *= nums[j]; // skip ourselves } answer.push(product); } return answer;}def product_except_self(nums): answer = [] for i in range(len(nums)): product = 1 for j in range(len(nums)): if j != i: product *= nums[j] # skip ourselves answer.append(product) return answerFor each of the n slots we walk all n numbers: n × n steps. With 4 numbers that’s 16, fine. With 100,000 numbers (LeetCode’s limit) it’s 10,000,000,000 steps. That’s O(n²), and it breaks the O(n) rule.
The waste: answer[2] multiplies 1 × 2, and then answer[3] multiplies 1 × 2
again (then × 3). We keep redoing the same left-hand products.
The “obvious” shortcut is: total product ÷ nums[i]. Interviewers ban it
because it hides the real skill (reusing partial products), and because of
zeros:
- One zero, like
[-1, 1, 0, -3, 3]: every slot except the zero’s own slot gets 0 (they all include the zero). The zero’s slot gets the product of the others, 9. Division would need 0 ÷ 0 there. - Two or more zeros, like
[0, 2, 0]: every slot includes at least one zero, so everything is 0.
Prefix and suffix products handle both cases with no special code. Play the zero examples in the visualizer below to see it.
Pattern
Prefix and suffix products (running totals)
Use it when: each position needs a summary of everything before it, after it, or both.
Signal words
- “except self”
- “everything to the left”
- “running total”
- “prefix sum”
- “range sum”
- “without division”
- Fill
answerwith 1s. Setprefix = 1(the product of nothing is 1, just as the sum of nothing is 0). - Pass 1, left to right. For each i: write
answer[i] = prefix(everything left of i), then updateprefix *= nums[i]so it’s ready for i + 1. - Set
suffix = 1. - Pass 2, right to left. For each i: multiply
answer[i] *= suffix(everything right of i), then updatesuffix *= nums[i]. - Return
answer.
Press Play. In pass 1 the shaded part of nums is what prefix has
multiplied so far; in pass 2 it’s what suffix has multiplied. Watch each
answer slot get its left half, then its right half. Then try the zero examples.
Prefix pass, then suffix pass
nums = [1, 2, 3, 4]
- 10
- 21
- 32
- 43
- 10
- 11
- 12
- 13
- pass
- —
- prefix
- 1product LEFT of i
- suffix
- —product RIGHT of i
- Looking at now
- Folded into prefix / suffix
- Just written
- Final value
Fill answer with 1s and set prefix = 1. prefix will always be the product of every number to the LEFT of i. Nothing is left of index 0, and multiplying by nothing gives 1.
Which line is running?
function productExceptSelf(nums) { const n = nums.length;Running now: const answer = new Array(n).fill(1); let prefix = 1; // product of everything LEFT of i for (let i = 0; i < n; i++) { answer[i] = prefix; prefix *= nums[i]; } let suffix = 1; // product of everything RIGHT of i for (let i = n - 1; i >= 0; i--) { answer[i] *= suffix; suffix *= nums[i]; } return answer;}The order inside each loop matters: write first, then fold in nums[i].
That’s what keeps nums[i] out of its own answer.
Prefix pass, then suffix pass
function productExceptSelf(nums) { const n = nums.length; const answer = new Array(n).fill(1); let prefix = 1; // product of everything LEFT of i for (let i = 0; i < n; i++) { answer[i] = prefix; prefix *= nums[i]; } let suffix = 1; // product of everything RIGHT of i for (let i = n - 1; i >= 0; i--) { answer[i] *= suffix; suffix *= nums[i]; } return answer;}def product_except_self(nums): n = len(nums) answer = [1] * n prefix = 1 # product of everything LEFT of i for i in range(n): answer[i] = prefix prefix *= nums[i] suffix = 1 # product of everything RIGHT of i for i in range(n - 1, -1, -1): answer[i] *= suffix suffix *= nums[i] return answerLines 1–7 match in both languages. After that JavaScript has extra closing braces, so its line numbers run ahead.
- Line 1: define the function. (LeetCode:
var productExceptSelf = function(nums)in JS,def productExceptSelf(self, nums)inclass Solutionin Python.) - Line 3: an array of n ones.
new Array(n).fill(1)/[1] * n. Starting at 1 matters: multiplying by 1 changes nothing. - Line 4:
prefixstarts at 1, because nothing is left of index 0. - Line 5: walk left to right.
- Line 6: store “everything left of i” in the answer slot.
nums[i]isn’t inprefixyet, which is exactly right. - Line 7: now include
nums[i], ready for the next index. - Lines 9–10 (JS) / lines 8–9 (Python):
suffixstarts at 1 and we walk from the last index down to 0. In Pythonrange(n - 1, -1, -1)means “start at n − 1, stop before −1, step −1”. - Line 11 (JS) / line 10 (Python): multiply in “everything right of i”.
Now
answer[i]is left × right, its final value. - Line 12 (JS) / line 11 (Python): include
nums[i]insuffixfor the next index to the left. - Last line: return the filled array.
| pass | i | write into answer[i] | then update | answer afterwards |
|---|---|---|---|---|
| 1 → | 0 | prefix = 1 | prefix = 1 × 1 = 1 | [1, 1, 1, 1] |
| 1 → | 1 | prefix = 1 | prefix = 1 × 2 = 2 | [1, 1, 1, 1] |
| 1 → | 2 | prefix = 2 | prefix = 2 × 3 = 6 | [1, 1, 2, 1] |
| 1 → | 3 | prefix = 6 | prefix = 6 × 4 = 24 | [1, 1, 2, 6] |
| 2 ← | 3 | 6 × suffix 1 = 6 | suffix = 1 × 4 = 4 | [1, 1, 2, 6] |
| 2 ← | 2 | 2 × suffix 4 = 8 | suffix = 4 × 3 = 12 | [1, 1, 8, 6] |
| 2 ← | 1 | 1 × suffix 12 = 12 | suffix = 12 × 2 = 24 | [1, 12, 8, 6] |
| 2 ← | 0 | 1 × suffix 24 = 24 | suffix = 24 × 1 = 24 | [24, 12, 8, 6] |
After pass 1 (its last row, i = 3) answer is [1, 1, 2, 6]: just the left halves. Pass 2
multiplies in the right halves from the end. The final products prefix = 24
and suffix = 24 are the total product, which we never use. That’s fine.
Brute force
Time
O(n²)
For each of n slots we multiply up to n numbers.
Space
O(1)
Just a running product, apart from the answer array.
Prefix pass, then suffix pass
Time
O(n)
Two passes over the array, each doing one write and one multiply per index. 100,000 numbers ≈ 200,000 steps.
Space
O(1) extra
Only prefix and suffix. The answer array is the required output, so LeetCode doesn't count it.
A common middle version builds two separate arrays, left[i] and right[i],
then multiplies them. That’s also O(n) time but uses O(n) extra space. Our
version stores the left products directly in answer and keeps the right product
in a single variable.
What to say out loud, in this order:
- “answer[i] is the product of everything to the left times everything to the right.”
- “Brute force recomputes these: O(n²). Running products reuse them.”
- “Two passes with one running variable each: O(n) time, O(1) extra space.”
- Explain why division fails with zeros, even if it weren’t banned.
Likely follow-up questions:
- “Can you do it with O(1) extra space?” Yes, the solution above: the left products live in the output array.
- “What about sums instead of products?” The same idea with prefix sums:
total − nums[i]works for sums, since subtraction has no zero problem. - “Range queries: product or sum of nums[l..r]?” Precompute a prefix array once, then each query is one subtraction (sums) or careful division (products).
Related problems:
- Two Sum and Contains Duplicate (this week): other “one pass, remember what you’ve passed” solutions.
- Best Time to Buy and Sell Stock (week 2): carries a running minimum from the left, the same “summary of everything before me” idea as
prefix. - Trapping Rain Water (not in this roadmap, but a classic): needs the tallest bar to the left and to the right of each position, a two-pass prefix/suffix problem just like this one.