Problem. Given nums, return answer where answer[i] is the product of every element except nums[i].
Do it in O(n) time without using division.
nums = [2, 3, 4, 5]
answer = [60, 40, 30, 24] # 3·4·5, 2·4·5, 2·3·5, 2·3·4
ML context. "Everything except me" is leave-one-out: leave-one-out cross-validation, the contribution of each feature when it's removed, or each sample's gradient compared against the rest of the batch. Computing all n "except me" results without redoing n full passes is exactly this trick.
It also reuses lesson 1.2's idea in a new shape: prefix (and now suffix) aggregates.
1. Step 1: Clarify
| Question | Answer | Why it matters |
|---|---|---|
| Division allowed? | No | Rules out "total / nums[i]" |
| Zeros possible? | Yes | Breaks division even when it's allowed |
| n? | Up to 10⁵ | O(n²) = 10¹⁰: too slow |
| Overflow? | Products fit (Python ints are unbounded anyway) | In fixed-width languages, ask |
| Extra space? | Ideally O(1) besides the output | Pushes us to reuse the output array |
2. Step 2: Brute force
For each position, multiply everything else.
def product_except_brute(nums):
n = len(nums)
answer = []
for i in range(n):
p = 1
for j in range(n):
if j != i:
p *= nums[j] # n − 1 multiplications per position
answer.append(p)
return answer
assert product_except_brute([2, 3, 4, 5]) == [60, 40, 30, 24]
assert product_except_brute([1, 0, 3]) == [0, 3, 0]
print("brute force works: O(n²) time, O(1) extra space")
O(n²) time. At n = 10⁵: about 10¹⁰ multiplications. Too slow.
Where's the repeated work? The answers for positions 2 and 3 both contain 2 · 3; every answer recomputes almost
the same product. We need to share it.
3. A tempting shortcut: divide the total
Compute the total product once, then answer[i] = total / nums[i]. O(n). But it breaks with zeros, and the
problem forbids division for a reason.
def product_except_division(nums):
zeros = nums.count(0)
total = 1
for x in nums:
if x != 0:
total *= x # product of the non-zero values
if zeros >= 2:
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] # exact for integers
assert product_except_division([2, 3, 4, 5]) == [60, 40, 30, 24]
assert product_except_division([1, 0, 3]) == [0, 3, 0]
assert product_except_division([0, 4, 0]) == [0, 0, 0]
print("division works only with three special cases")
Three special cases is a smell: the approach doesn't match the problem. It also fails for floats (rounding) and when division isn't defined at all (some algebraic types, or a forbidden operation). Let's find one rule that always works.
4. Step 3: Optimise: split "everything else" in two
First principles. "Every element except index i" is everything to the left of i times everything to the right of i. Both halves are running products, which we can build in one pass each, exactly like prefix sums.
import random
def product_except_prefix_suffix(nums):
n = len(nums)
left = [1] * n # left[i] = product of nums[0..i-1]
right = [1] * n # right[i] = product of nums[i+1..n-1]
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)]
def brute(nums):
out = []
for i in range(len(nums)):
p = 1
for j, x in enumerate(nums):
if j != i:
p *= x
out.append(p)
return out
assert product_except_prefix_suffix([2, 3, 4, 5]) == [60, 40, 30, 24]
rng = random.Random(17)
for _ in range(1000):
nums = [rng.randint(-3, 3) for _ in range(rng.randint(1, 10))] # plenty of zeros
assert product_except_prefix_suffix(nums) == brute(nums)
print("prefix × suffix: O(n) time, O(n) extra, no division, zeros handled for free")
- Time: O(n): three passes.
- Extra space: O(n) for
leftandright. - Zeros need no special case: a zero simply makes every prefix or suffix that contains it zero, which is the correct answer. One rule covers every input.
Quick check
Why does the prefix × suffix method handle zeros with no special cases?
Show the answer
B. Each answer is literally the product of the left part times the right part, so a zero appears in exactly the products that should contain it; no division ever happens — Avoiding division means there's no 'divide by zero' situation to patch.
Optimisation 2: O(1) extra space
The constraint "O(1) extra space (the output array doesn't count)" asks: do we need both helper arrays?
- Write the prefix products directly into the output.
- Then walk right to left with a single variable
right, the running suffix product, and multiply it in.
import random
def product_except_self(nums):
n = len(nums)
out = [1] * n
for i in range(1, n): # pass 1: out[i] = product left of i
out[i] = out[i - 1] * nums[i - 1]
right = 1
for i in range(n - 1, -1, -1): # pass 2: multiply in the product right of i
out[i] *= right
right *= nums[i]
return out
def brute(nums):
out = []
for i in range(len(nums)):
p = 1
for j, x in enumerate(nums):
if j != i:
p *= x
out.append(p)
return out
assert product_except_self([2, 3, 4, 5]) == [60, 40, 30, 24]
assert product_except_self([7]) == [1] # empty product is 1
rng = random.Random(18)
for _ in range(1000):
nums = [rng.randint(-3, 3) for _ in range(rng.randint(1, 10))]
assert product_except_self(nums) == brute(nums)
print("two passes, one running variable: O(n) time, O(1) extra space")
- Time: O(n). Extra space: O(1) beyond the output.
- The order inside pass 2 matters: use
rightbefore multiplying innums[i], so position i never includes itself. That's the same "update after use" care as lesson 1.4.
5. When the constraints change
| If the constraint becomes… | Best approach | Time | Extra space |
|---|---|---|---|
| Division forbidden (classic) | Prefix × suffix | O(n) | O(n) |
| O(1) extra space | Prefix in output + running suffix | O(n) | O(1) |
| Division allowed, ints | Total ÷ nums[i] with zero cases | O(n) | O(1) |
| Sum except self | total − nums[i] (subtraction is safe) | O(n) | O(1) |
| Floats with huge/tiny products | Sum of logs (track signs and zeros) | O(n) | O(1) |
| Except a window around i | Prefix/suffix over blocks, or a sliding structure | O(n) | O(n) |
| Many queries "product of range [l, r]" | Prefix products (no zeros) or a segment tree (module 14) | O(1) / O(log n) per query | O(n) |
Change A: "sum except self"
Subtraction always exists and never fails on zero, so the shortcut becomes safe: total − nums[i]. The operation's
properties decide the algorithm. Products lack a safe inverse (zero has none); sums have one.
Change B: floats whose product overflows or underflows
Multiplying many probabilities underflows to 0.0. The standard ML fix is to work in log space: products become
sums of logs. Track zeros and signs separately, since log is defined only for positive values.
import math
def product_except_self_log(probs):
"""Leave-one-out product of positive probabilities, returned as log-probabilities."""
logs = [math.log(p) for p in probs] # all p > 0 here
total = sum(logs)
return [total - lp for lp in logs] # 'sum except self' in log space
probs = [1e-200, 1e-200, 0.5]
naive = probs[0] * probs[1] * probs[2]
assert naive == 0.0 # underflow: the real value is 5e-401
log_answers = product_except_self_log(probs)
assert abs(log_answers[2] - (-400 * math.log(10))) < 1e-9 # log(1e-200 · 1e-200), no underflow
assert abs(math.exp(log_answers[0]) - 0.5e-200) < 1e-210 # 1e-200 · 0.5 is still representable
print("log space turns products into sums: no underflow")
The log trick turns "product except self" into "sum except self", where subtraction is safe again. That's the same reason language models sum log-probabilities instead of multiplying probabilities.
Change C: leave-one-out statistics in ML
The prefix/suffix idea computes any associative "everything except me" aggregate: sums, products, max, min. For leave-one-out maximums (which have no inverse operation), prefix and suffix maxima are the only O(n) route:
def max_except_self(nums):
n = len(nums)
left = [float("-inf")] * n
right = [float("-inf")] * n
for i in range(1, n):
left[i] = max(left[i - 1], nums[i - 1])
for i in range(n - 2, -1, -1):
right[i] = max(right[i + 1], nums[i + 1])
return [max(left[i], right[i]) for i in range(n)]
scores = [0.2, 0.9, 0.4, 0.7]
assert max_except_self(scores) == [0.9, 0.7, 0.9, 0.9]
print("prefix/suffix works for max too, where no inverse exists")
This is the general lesson: when an aggregate has no inverse, split "except me" into "left of me" and "right of me".
Quick check
Why is 'sum except self' easy with total − nums[i], but 'product except self' needs prefix and suffix products?
Show the answer
A. Subtraction always undoes addition, but division can't undo multiplication by zero (and may be forbidden); without a safe inverse, combine left and right parts instead — Whether the operation has an inverse decides whether a total-minus-self shortcut exists.
6. Saying it out loud
"Brute force multiplies everything else for each position: O(n²). Dividing the total needs three zero cases and is forbidden here. Instead, the answer at i is the product to its left times the product to its right: prefix and suffix products, O(n). For O(1) extra space I write the prefix products into the output, then sweep right to left with one running suffix variable. For sums I'd just subtract; for float underflow I'd use log space."
Check yourself
- Where is the repeated work in the brute force?
- What are the three zero cases of the division approach, and why are they a smell?
- Why does "left of i times right of i" give the answer, and how are both parts computed?
- How does the O(1) version avoid storing the suffix array?
- Why must
out[i] *= rightcome beforeright *= nums[i]? - When is "total minus self" safe, and what's the fallback when it isn't?
Answers
- Every answer recomputes nearly the same product; neighbouring answers share almost all their factors.
- No zeros (divide), one zero (only that slot is non-zero), two or more (all zero). Special cases mean the method doesn't fit the problem's structure.
- "Everything except i" is exactly the left part times the right part; each is a running product built in one pass.
- It writes prefix products into the output, then multiplies in a single running suffix variable from right to left.
- So
rightholds the product strictly to the right of i, never includingnums[i]itself. - When the operation has a safe inverse (addition/subtraction, or products in log space without zeros); otherwise combine prefix and suffix aggregates.