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. A single all-elements product can overflow. In fixed-width arithmetic, total may overflow even when some products that exclude one element would fit. Prefix/suffix avoids computing that particular total, but it does not eliminate overflow in general; the input contract or a wider numeric type must still make every intermediate product safe.

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: Output-backed - O(n) time, O(1) auxiliary 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 removes the two auxiliary arrays: the output stores prefixes, then a right-to-left pass multiplies in a running suffix. It still makes two directional passes; it does not combine them into one.

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 moves beyond the earlier hashing lessons (Days 4, 5, 11, and 12): “have I seen this?”, “how many times?”, “what’s the complement?”, and “what’s the canonical form?” Not every lesson in Days 4-12 used a hash map. Here there is no lookup; the answer comes from your position in the array.

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

• Sliding window (introduced later in the challenge): 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?