VFlash: Fast, Accurate Visual Planning via Flash Primitive Decoding
u_Unrolled
DSA for AI/ML · Module 01: Arrays and strings

Lesson 1.8 of 16 in this moduleFree

Product of Array Except Self

For each position, the product of every other value, without division: from an O(n²) brute force, through the division shortcut and its zero cases, to prefix and suffix products in O(n), then O(1) extra space. Then what changes with sums, log space, sliding windows and leave-one-out in ML.

about 10 min 6 Python examples 2 quick checks

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.

text
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.

python
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.

three cases for the division approach: no zeros, where total / nums[i] works; exactly one zero, where only the zero's slot is non-zero; two or more zeros, where every answer is 0.
Diagram— three cases for the division approach: no zeros, where total / nums[i] works; exactly one zero, where only the zero's slot is non-zero; two or more zeros, where every answer is 0.
python
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.

for [2, 3, 4, 5], the prefix row [1, 2, 6, 24] holds products to the left of each index, the suffix row [60, 20, 5, 1] holds products to the right, and multiplying them gives [60, 40, 30, 24].
Diagram— for [2, 3, 4, 5], the prefix row [1, 2, 6, 24] holds products to the left of each index, the suffix row [60, 20, 5, 1] holds products to the right, and multiplying them gives [60, 40, 30, 24].
python
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 left and right.
  • 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?

  1. It skips zeros
  2. 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
  3. It replaces zeros with ones
  4. It doesn't; you need the three 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.
pass 1 fills the output with prefix products [1, 2, 6, 24]; pass 2 walks right to left with the running suffix 1, 5, 20, 60, giving [60, 40, 30, 24].
Diagram— pass 1 fills the output with prefix products [1, 2, 6, 24]; pass 2 walks right to left with the running suffix 1, 5, 20, 60, giving [60, 40, 30, 24].
python
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 right before multiplying in nums[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.

python
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:

python
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?

  1. 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
  2. Sums are faster
  3. Products are bigger
  4. There's no difference
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

  1. Where is the repeated work in the brute force?
  2. What are the three zero cases of the division approach, and why are they a smell?
  3. Why does "left of i times right of i" give the answer, and how are both parts computed?
  4. How does the O(1) version avoid storing the suffix array?
  5. Why must out[i] *= right come before right *= nums[i]?
  6. When is "total minus self" safe, and what's the fallback when it isn't?
Answers
  1. Every answer recomputes nearly the same product; neighbouring answers share almost all their factors.
  2. 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.
  3. "Everything except i" is exactly the left part times the right part; each is a running product built in one pass.
  4. It writes prefix products into the output, then multiplies in a single running suffix variable from right to left.
  5. So right holds the product strictly to the right of i, never including nums[i] itself.
  6. When the operation has a safe inverse (addition/subtraction, or products in log space without zeros); otherwise combine prefix and suffix aggregates.