Product of Array Except Self
Each answer is the product of everything to its left times everything to its right.
Two-Pass Trace
Problem
Given an integer array, create a new array where position i contains the product of every input value except nums[i]. Do not use division, and design the algorithm to run in linear time with only constant extra memory beyond the returned array.
Examples
Input: nums = [1, 2, 3, 4]
Output: [24, 12, 8, 6]
Input: nums = [0, 2, 3, 4]
Output: [24, 0, 0, 0]
The Goal
Return an array where output[i] is the product of every number in nums except nums[i], without using division.
For [1, 2, 3, 4], the answer is [24, 12, 8, 6]. At index 2, that's (1 × 2) × 4 = 8.
Each answer is the product of everything left of i times everything right of it.
Left times right
output[i] is the product of the numbers before i times the product of the numbers after i.
Two running products, one from each end, build every answer.
Key Idea: Prefix and Suffix Products
Walk left to right keeping prefix, the product of everything before i. Write it into output[i], then multiply nums[i] in.
Then walk right to left keeping suffix, the product of everything after i, and multiply it into output[i].
An empty side multiplies by 1, so both start at 1.
output[i] gets the product of everything left of i.
[1, 2, 3, 4] gives [1, 1, 2, 6]
The Algorithm
n = len(nums)
output = [1] * n
prefix = 1
for i in range(n):
output[i] = prefix
prefix *= nums[i]
suffix = 1
for i in range(n - 1, -1, -1):
output[i] *= suffix
suffix *= nums[i]
return outputWrite output[i] before multiplying nums[i] into the running product. The other way round puts nums[i] into its own answer.
| Approach | Time | Extra space | With a zero |
|---|---|---|---|
| Two passes | O(n) | O(1) | Works |
| Prefix and suffix arrays | O(n) | O(n) | Works |
| Total product, then divide | O(n) | O(1) | Breaks |
| Multiply the rest each time | O(n^2) | O(1) | Works |
Walkthrough
Run it on [1, 2, 3, 4].
The first pass writes the products of everything to the left, [1, 1, 2, 6], and prefix ends at 24. The second pass multiplies in the products of everything to the right: 1 at index 3, then 4, 12 and 24. That gives [24, 12, 8, 6].
The brackets under nums show what prefix and suffix cover at each step.
Checkpoint · predict the next step
Step 7 of 19 on the stage: prefix = 2 × 3 = 6, now through index 2.
i on 3 (index 2) · output = [1, 1, 2, 1] · prefix 6
Pitfalls
- Dividing the total by
nums[i]fails on a zero, and the problem rules division out anyway. - With one zero, every other answer is 0, and the zero's own answer is the product of the rest:
[1, 2, 0, 4]gives[0, 0, 8, 0]. - With two zeros, every answer is 0.
- The second loop has to reach index 0:
range(n - 1, -1, -1).
Why not divide the product of all the numbers by nums[i]?
Complexity
Two passes over n numbers, each step one write and one multiply: O(n) time.
Apart from output, which the problem asks for, you keep two numbers, so extra space is O(1).
Two passes, no division
- Prefix passOne write and one multiply per index.dominantO(n)
- Suffix passThe same, from the right.dominantO(n)
- prefix and suffixTwo numbers.O(1)
| n | 10 | 100 | 1,000 | 10,000 |
|---|---|---|---|---|
| O(n) | 10 | 100 | 1K | 10K |
Two passes, and the output is the only array.
In short
Without division, build the answer in two sweeps: a left-to-right pass filling each slot with the running prefix product, then a right-to-left pass multiplying in the running suffix product. The output array doubles as scratch space for O(1) extra memory.
Common mistake
Using division to divide the total product by each element — it breaks when the array contains a zero.