Appearance
4.4.7 — Product of Array Except Self
LeetCode 238 · Medium · ★ Blind 75
The problem
You are given a list of numbers called nums. Build a new list called answer. At each position i, answer[i] must be the product of every number in nums except nums[i]. A product is what you get when you multiply numbers together.
nums = [1, 2, 3, 4]
answer = [24, 12, 8, 6]
nums = [-1, 1, 0, -3, 3]
answer = [ 0, 0, 9, 0, 0]Look at the first example. answer[0] skips the 1 and multiplies the rest: 2 \times 3 \times 4 = 24. answer[1] skips the 2: 1 \times 3 \times 4 = 12. And so on.
The list can have up to 100,000 numbers. There are two hard rules. You may not use division, and the solution must run in O(n) time. A follow-up asks you to use only O(1) extra memory, not counting the answer list itself.
What the problem is really asking
Pick any position, say position 2 in [1, 2, 3, 4]. The numbers that are not at position 2 fall into two groups.
- The numbers to its left: 1 and 2.
- The numbers to its right: 4.
So the answer at position 2 is (product of everything on the left) times (product of everything on the right) = (1 \times 2) \times 4 = 8.
That is true at every position. We can write it as one formula:
\text{answer}[i] = \Big(\prod_{j < i} \text{nums}[j]\Big) \times \Big(\prod_{j > i} \text{nums}[j]\Big)
Read it aloud like this. The big \prod sign, the Greek capital letter "pi", means "multiply together". So the first bracket says "multiply together nums[j] for every position j that is less than i", which is everything to the left. The second bracket does the same for every j greater than i, which is everything to the right.
So the problem is really: for every position, find the product of its left side and the product of its right side.
Why division is banned
Without the rule, there is a two-line answer. Multiply everything together once, then divide by each number in turn. For [1, 2, 3, 4] the total is 24, and 24 \div 2 = 12, which is correct.
But one zero breaks it. Dividing by zero is not allowed. To handle zeros properly you need three separate cases: no zeros, exactly one zero, or two or more zeros. Each case needs its own code.
The solution on this page has no special cases at all. Zeros and negative numbers go through the same lines as everything else. So the rule is not just a puzzle. It is pushing you toward a cleaner design.
The brute force, and where it wastes work
For each position, multiply all the other numbers.
python
def productExceptSelf(nums):
n = len(nums)
answer = []
for i in range(n):
p = 1
for j in range(n):
if j != i: # skip the number at position i
p *= nums[j]
answer.append(p)
return answerThis does n multiplications for each of n positions, so about n^2 steps. For 100,000 numbers that is ten billion steps. Too slow.
The waste in one sentence: the product of everything left of position 5 is just the product of everything left of position 4, times one more number, but the brute force multiplies it all again from scratch.
The idea
Think of a train picking up passengers. To know how many people are on the train when it leaves station 5, you do not go back and count everyone who boarded at stations 1, 2, 3 and 4. You take the number who were on board leaving station 4, and add the people who got on at station 5.
We do the same with multiplication. Walk left to right, carrying a running product called prefix. At each position, prefix already holds the product of everything to the left. Write it down, then multiply in the current number so it is ready for the next position.
Then do the same thing from right to left with a running product called suffix, for everything to the right.
The figure shows both sweeps on [1, 2, 3, 4].
Here is how to read it.
- The top row is
nums. - Row ① is the left-to-right sweep. Each blue box holds the product of everything to the left of that position. The first box is 1, because nothing is to the left of position 0.
- Row ② is the right-to-left sweep. Each amber box holds the product of everything to the right. The last box is 1, because nothing is to the right of the last position.
- Row ③ multiplies ① and ② position by position: 1 \times 24 = 24, 1 \times 12 = 12, 2 \times 4 = 8, 6 \times 1 = 6. That is the answer.
Why does the first left product start at 1 and not at nums[0]? Because there is nothing to the left of position 0. The product of no numbers at all is 1, in the same way that the sum of no numbers is 0. Multiplying by 1 changes nothing. Starting at 1 means position 0 needs no special if.
The solution
python
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
n = len(nums)
answer = [1] * n # (1)
prefix = 1 # (2)
for i in range(n): # (3)
answer[i] = prefix # (4)
prefix *= nums[i] # (5)
suffix = 1 # (6)
for i in range(n - 1, -1, -1): # (7)
answer[i] *= suffix # (8)
suffix *= nums[i] # (9)
return answerts
function productExceptSelf(nums: number[]): number[] {
const n = nums.length;
const answer = new Array(n).fill(1); // (1)
let prefix = 1; // (2)
for (let i = 0; i < n; i++) { // (3)
answer[i] = prefix; // (4)
prefix *= nums[i]; // (5)
}
let suffix = 1; // (6)
for (let i = n - 1; i >= 0; i--) { // (7)
answer[i] *= suffix; // (8)
suffix *= nums[i]; // (9)
}
return answer;
}Line by line
(1) answer = [1] * n. The output list, filled with 1s. The first sweep will overwrite every slot, so the starting value does not really matter here. Using 1 is a safe habit, because we will later multiply into these slots.
(2) prefix = 1. The running product of everything to the left of the current position. Before position 0, nothing is to the left, so it starts at 1.
(3) Sweep left to right, over positions 0, 1, 2, and so on.
(4) answer[i] = prefix. At this moment, prefix holds the product of every number before position i. It does not yet include nums[i]. So we write it into the answer slot.
(5) prefix *= nums[i]. Now fold the current number in. prefix becomes the product of everything up to and including position i, which is exactly "everything to the left" for the next position.
The order of lines (4) and (5) is the whole trick. If you swap them, prefix already includes nums[i] when you write it down. Every slot would then include its own number, which is the one thing the problem says to leave out.
(6) suffix = 1. The running product of everything to the right. Nothing is to the right of the last position, so it starts at 1.
(7) Sweep right to left. range(n - 1, -1, -1) counts down from the last position, n - 1, to 0. The middle number, -1, is where to stop, and Python stops before it, so 0 is the last position visited. The third number, -1, means "step backwards by one".
(8) answer[i] *= suffix. The slot already holds the left product from the first sweep. We multiply in the right product. Now the slot holds left times right, which is the final answer for this position.
(9) suffix *= nums[i]. Fold the current number in, ready for the position to its left. Same discipline as lines (4) and (5): use it, then update it.
A helpful way to remember both loops is to say this sentence before writing them: "prefix is the product of everything strictly before i, and suffix is the product of everything strictly after i." Then each loop is simply "use the value, then update it".
Trace
Take nums = [1, 2, 3, 4].
First sweep, left to right.
i | prefix before | answer[i] set to | prefix after |
|---|---|---|---|
| 0 | 1 | 1 | 1 × 1 = 1 |
| 1 | 1 | 1 | 1 × 2 = 2 |
| 2 | 2 | 2 | 2 × 3 = 6 |
| 3 | 6 | 6 | 6 × 4 = 24 |
Now answer is [1, 1, 2, 6].
Second sweep, right to left.
i | suffix before | answer[i] becomes | suffix after |
|---|---|---|---|
| 3 | 1 | 6 × 1 = 6 | 1 × 4 = 4 |
| 2 | 4 | 2 × 4 = 8 | 4 × 3 = 12 |
| 1 | 12 | 1 × 12 = 12 | 12 × 2 = 24 |
| 0 | 24 | 1 × 24 = 24 | 24 × 1 = 24 |
The final answer is [24, 12, 8, 6].
Why zeros need no special case
Take nums = [1, 0, 3].
- The first sweep gives
[1, 1, 0]. The 0 only entersprefixafter position 1 has been written. - The second sweep multiplies in the right-hand products
[0, 3, 1]. - The result is
[1 × 0, 1 × 3, 0 × 1] = [0, 3, 0].
Check it by hand. Skipping position 0 gives 0 \times 3 = 0. Skipping position 1 gives 1 \times 3 = 3. Skipping position 2 gives 1 \times 0 = 0. All correct.
The zero lands in exactly the slots that should see it, and never in its own slot. That is because no sweep ever multiplies nums[i] into answer[i]. Lines (4) and (8) always write before lines (5) and (9) update. Two zeros give all zeros for the same reason. Negative numbers just multiply like any other number.
Complexity, derived
Time. The first loop runs n times, and each turn does one assignment and one multiplication. The second loop also runs n times with one multiplication and one update. So the total is about 2n small steps. We drop the constant 2, because only the growth matters, and get O(n).
Space. The answer list has n slots, but the problem says the output does not count as extra memory. Apart from it, we only use two numbers, prefix and suffix. So the extra memory is O(1).
A gentler first version builds two separate lists, left[] and right[], and then multiplies them. That is easier to read but uses O(n) extra memory. It is a perfectly good first answer in an interview. Then show how to fold left[] into answer and replace right[] with one variable. Showing the improvement step by step is better than jumping to the tight version.
Edge cases
- Two numbers, the smallest input allowed.
[a, b]gives[b, a]. - One zero. Every slot except the zero's own slot becomes 0.
- Two or more zeros. Every slot becomes 0.
- Overflow. The problem promises that every left product and right product fits in a 32-bit whole number. That promise is about the running products, not only the final answers, because those are what could grow too large. Python and JavaScript numbers do not overflow at this size. In Java or C++ they could.
Variations you will meet
- Prefix sums. The same two-sweep idea with addition instead of multiplication. See 4.2.
- Trapping Rain Water. The water above each bar is limited by the tallest bar on its left and the tallest bar on its right. That is this exact structure with
maxinstead of×. See 4.5.5. - Candy. Children in a row must get more sweets than a neighbour with a higher rating. One sweep handles the left neighbour rule, one sweep handles the right neighbour rule, and each child gets the larger of the two.
The general lesson: when the answer at each position depends on everything before it and everything after it, do one sweep in each direction and choose the operation that fits the question.
What the interviewer will push on
"Why forbid division?" They want to see that you understand zeros. Division needs three separate cases for zeros. This solution needs none.
"Can you do it in O(1) extra memory?" Use the output list to hold the left products, and keep the right product in one variable.
"What if the numbers were decimals?" Even without zeros, division stops being safe. Decimal multiplication and division on a computer are not exact opposites, so small rounding errors creep in. This solution never divides.
"What if the list keeps changing, and you must answer many queries?" Every change would spoil the two sweeps. The right tool becomes a segment tree, which can update one number and answer a product query in O(\log n) time. See 4.13.4.
One thing to volunteer: say the rule about prefix and suffix out loud before writing the loops. That is how you know the code is correct, rather than hoping the examples pass.
Next: 4.4.8 Valid Sudoku. Back to sets, where the interesting part is how to name a region of a grid with one number.