Product of array except self — prefix × suffix

Day 18 asked “which elements appear most?” — a ranking problem solved with a heap. Day 19 asks something that feels like it needs division: “what is the product of everything except me?” The constraint — no division allowed — forces a reframe that teaches one of the most important array techniques in all of algorithms: prefix and suffix products.

The problem

Given an integer array nums, return an array answer where answer[i] is the product of all elements in nums except nums[i].

Example: nums = [1, 2, 3, 4] → answer = [24, 12, 8, 6]

Constraints: O(n) time. No division. (The no-division rule kills the obvious approach — multiply everything, then divide by nums[i].)

Why “no division” matters

The division approach: compute total = 1 × 2 × 3 × 4 = 24, then answer[i] = total / nums[i]. Simple. But it breaks on two real-world cases:

1. Zeroes. If nums = [0, 2, 3], total = 0. 0 / 0 is NaN. You’d need special handling: count zeroes, and if there’s exactly one, every element’s answer is 0 except the zero’s position (which gets the product of non-zero elements). Messy.
2. Integer overflow. In languages with fixed-width integers (Java, C++), total can overflow before you divide. The prefix/suffix approach distributes the multiplication, keeping intermediate values smaller.

The no-division constraint isn’t arbitrary — it reflects a real engineering concern. And it forces you to discover a more powerful technique.

The reframe: before me × after me

For each position i, the product of everything except nums[i] is:

answer[i] = (product of everything BEFORE i) × (product of everything AFTER i)

This is the key insight. Let’s call them prefix (product of elements before index i) and suffix (product of elements after index i).

For nums = [1, 2, 3, 4]:

prefix  = [1, 1, 2, 6]     (prefix[0] = 1, prefix[i] = prefix[i-1] × nums[i-1])
suffix  = [24, 12, 4, 1]   (suffix[3] = 1, suffix[i] = suffix[i+1] × nums[i+1])
answer  = [24, 12, 8, 6]   (answer[i] = prefix[i] × suffix[i])

Verify index 2: prefix[2] × suffix[2] = 2 × 4 = 8. ✓

Approach 1: Brute force — O(n²) time, O(1) space

For each index, multiply all the other elements.

function productExceptSelf(nums) {
  const n = nums.length;
  const answer = new Array(n).fill(1);
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (i !== j) answer[i] *= nums[j];
    }
  }
  return answer;
}

Time: O(n²) — nested loops. Space: O(1) extra (not counting output).

At n=100,000, this takes 8,736ms. Unusable.

Approach 2: Prefix and suffix arrays — O(n) time, O(n) space

Two passes. First pass: build prefix array left-to-right. Second pass: build suffix array right-to-left. Multiply.

function productExceptSelf(nums) {
  const n = nums.length;
  const prefix = new Array(n);
  const suffix = new Array(n);
  const answer = new Array(n);

  // Prefix: product of everything before i
  prefix[0] = 1;
  for (let i = 1; i < n; i++) {
    prefix[i] = prefix[i - 1] * nums[i - 1];
  }

  // Suffix: product of everything after i
  suffix[n - 1] = 1;
  for (let i = n - 2; i >= 0; i--) {
    suffix[i] = suffix[i + 1] * nums[i + 1];
  }

  // Answer: prefix × suffix
  for (let i = 0; i < n; i++) {
    answer[i] = prefix[i] * suffix[i];
  }
  return answer;
}

Time: O(n) — three passes. Space: O(n) — two extra arrays.

At n=100,000: 1.563ms — 5,589× faster than brute force.

Approach 3: In-place — O(n) time, O(1) space

The optimization: instead of storing prefix and suffix arrays, use the output array itself. First pass fills it with prefix products. Second pass multiplies by a running suffix product.

function productExceptSelf(nums) {
  const n = nums.length;
  const answer = new Array(n);

  // Pass 1: fill answer with prefix products
  answer[0] = 1;
  for (let i = 1; i < n; i++) {
    answer[i] = answer[i - 1] * nums[i - 1];
  }

  // Pass 2: multiply by running suffix product
  let suffix = 1;
  for (let i = n - 1; i >= 0; i--) {
    answer[i] *= suffix;
    suffix *= nums[i];
  }
  return answer;
}

Time: O(n) — two passes. Space: O(1) extra (the output array doesn’t count).

At n=100,000: 0.676ms — 2.3× faster than prefix/suffix arrays, and 12,923× faster than brute force.

The in-place optimization mirrors Day 11’s one-pass Two Sum: combine two passes into one by maintaining a running variable. Same principle, different problem.

Real benchmark (30 runs, median)

n	Brute O(n²)	Prefix/Suffix O(n)	In-place O(n)
100	0.011ms	0.002ms	0.001ms
1,000	0.880ms	0.016ms	0.009ms
10,000	94.7ms	0.184ms	0.089ms
50,000	2,461ms	0.841ms	0.353ms
100,000	8,736ms	1.563ms	0.676ms

The in-place variant wins at every size — it saves one array allocation and has better cache locality (single array, sequential access).

How this connects to the pattern family

This problem breaks the hash pattern. Days 4-12 all used hash maps: “have I seen this?”, “how many times?”, “what’s the complement?”, “what’s the canonical form?” This problem has no lookup. The answer isn’t in what you’ve seen — it’s in your position in the array.

The prefix/suffix technique is a new tool: positional computation. It generalizes to:

• Sliding window (Day 20+): maintain a running sum/product over a window
• Range sum queries: prefix sums let you compute sum(i,j) in O(1)
• Trapping rain water: prefix max from left, suffix max from right

Transfer questions

1. You’re given an array of daily stock prices. For each day, compute the maximum profit you could make by buying on any previous day and selling today — in O(n) time. (Hint: what’s the “prefix” here?)
2. The prefix/suffix approach works for products. What happens if the array contains a zero? Two zeroes? Does the algorithm still produce correct results, and if so, why?