The problem
Given a list of numbers, build a new list where each position holds the product of all the other numbers (everything except itself). Division is not allowed.
Input: [1, 2, 3, 4] Output: [24, 12, 8, 6] (e.g. 24 = 2·3·4)
Picture it
Picture people standing in a row, each holding a number. A runner walks left to right carrying the product of everyone they have passed, and writes that onto each person’s card before multiplying in that person’s number. A second runner walks back from the right doing the same. Each card ends up holding (everything to my left) × (everything to my right), which is everyone except me.
How to recognise it
- Each position needs a summary of everything except itself (a product, sum, maximum).
- "Everything except i" splits into two parts: everything to the left and everything to the right.
- The easy shortcut (total ÷ nums[i]) is forbidden, and it would break on zeros anyway.
- n is up to 10^5, so recomputing the product for every position is too slow.
Start with brute force
For every position, multiply all the other numbers together.
def product_except_self_brute(nums):
n = len(nums)
out = []
for i in range(n):
p = 1
for j in range(n):
if j != i:
p *= nums[j]
out.append(p)
return out
That is n − 1 multiplications for each of n positions: O(n²) time and O(1) extra space besides the output. With n = 10^5 it is about 10^10 multiplications, far too slow.
From brute force to the idea
- Find the waste. Position 5 and position 6 share almost all their work: both multiply nums[0] to nums[4] on the left, and both multiply the numbers after 6 on the right.
- Split the product. The answer at i is (product of everything left of i) × (product of everything right of i).
- Left products in one pass. Walk left to right with a running product
left. Write it intoout[i]before multiplying in nums[i], so position i only sees what is strictly to its left. - Right products in a second pass. Walk right to left with a running product
right, multiplying it intoout[i]before multiplying in nums[i]. - No extra arrays. The output list holds the left products, and
rightis a single number. LeetCode does not count the output as extra space, so this meets the follow-up of O(1) extra space.
This is the key idea: answer = prefix product × suffix product, built with two running products.
The key idea
Answer[i] = prefix product before i × suffix product after i. Two passes, no division, O(n) time.
Python solution
def product_except_self(nums):
n = len(nums)
out = [1] * n
left = 1
for i in range(n):
out[i] = left # product of everything on the left
left *= nums[i]
right = 1
for i in range(n - 1, -1, -1):
out[i] *= right # times everything on the right
right *= nums[i]
return outIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n²): each position multiplies n − 1 numbers | O(1) extra besides the output |
| Two running products (shown code) | O(n): two passes, one multiplication each per position | O(1) extra besides the output: left and right |
Edge cases
- One zero (
[-1, 1, 0, -3, 3]): returns[0, 0, 9, 0, 0]. Only the zero's own position escapes the zero. - Two or more zeros (
[0, 0, 2]): every position includes at least one zero, so the result is all zeros. - Negative numbers: handled by ordinary multiplication; no special case.
- Two numbers (
[2, 3]): returns[3, 2], the minimum LeetCode allows. - One number or empty list: returns
[1]and[]. These are outside LeetCode's limits (n ≥ 2);[1]is the empty product. - Overflow: LeetCode promises every prefix and suffix product fits in 32 bits. Python integers never overflow anyway.
Common mistakes
- Multiplying
left *= nums[i]before writingout[i] = left, so each position includes itself. For[1, 2, 3, 4]that returns[24, 24, 24, 24]. - Using division and then special-casing zeros, which the problem forbids.
- Building separate
prefixandsuffixarrays. Correct and O(n), but it uses O(n) extra space that the follow-up asks you to avoid.
Now suppose division is allowed. Solve the same problem with a total product and division, and make it correct when the list contains zeros. Describe your approach, then write it if you like.
Compare with our answer
Count the zeros and multiply all the non-zero numbers. Two or more zeros make every answer 0. Exactly one zero means only that position gets the product of the others; everything else is 0. With no zeros, divide the total by each number.
def product_with_division(nums):
zeros = nums.count(0)
total = 1
for x in nums:
if x != 0:
total *= x
if zeros > 1:
return [0] * len(nums)
if zeros == 1:
return [total if x == 0 else 0 for x in nums]
return [total // x for x in nums]
total // x is exact here because x divides the total. Time O(n), extra space O(1).
A strong answer mentions: the three zero cases, multiplying only the non-zero numbers, and that integer division is exact because each x is a factor of the total.
1. For each day you must report the highest temperature on any other day. Which approach fits best?
"Everything except i" splits into a left part and a right part, and both can be precomputed with running maxima. Sorting gives the wrong answer for the hottest day itself, and recomputing is O(n²).
2. Why does the shown code use O(1) extra space even though it returns a list of n numbers?
By convention the returned list is not counted as extra space. The left products are written straight into it, and the right side needs only one running number.
3. A learner swaps the two lines of the first loop, so left *= nums[i] runs before out[i] = left. What does the function return for [1, 2, 3, 4]?
With the swap, out[i] holds the product up to and including i. The second pass multiplies in everything to the right, so every position gets the full product, 24.
Score 60% or more and the lesson is marked complete.