Things

Product of Array Except Self (LC 238)

4 min read

Pattern: Prefix / suffix products → left of me × right of me
Difficulty: Medium
Time: O(n) | Space: O(1) extra (the output array doesn’t count)

Problem

Given nums, return answer where answer[i] is the product of every element except nums[i].
Rules: no division, O(n) time. Follow-up: O(1) extra space.

nums = [1,2,3,4] → [24,12,8,6]
nums = [-1,1,0,-3,3] → [0,0,9,0,0]

Core idea

Everything except me = everything to my left × everything to my right.

For [1,2,3,4] at index 2 (the 3): left is 1×2 = 2, right is 4, answer 8.

Both sides can be built in one pass each as running products, the same way a running total builds prefix sums. Brute force (multiply everything else for each i) is O(n²).

Why not divide?

“Multiply everything, then divide by nums[i]” breaks on zeros. Real output in JS:

[-1,1,0,-3,3]  →  [-0, 0, NaN, -0, 0]   (should be 9 at the zero)
[0,0,2]        →  [NaN, NaN, 0]        (should be all 0)

You’d need special cases for one zero and for two or more zeros. The problem bans division to push you to the prefix/suffix idea instead.

My first version

Inclusive arrays: prefix[i] and suffix[i] include nums[i], so the answer is prefix[i-1] * suffix[i+1]. Both indexes fall off the ends, which forces three cases.

function productExceptSelf(nums: number[]): number[] {
  const len = nums.length;
  const prefix: number[] = new Array(len).fill(1);
  const suffix: number[] = new Array(len).fill(1);
 
  for (let i = 0; i < len; i++) {
    prefix[i] = i === 0 ? nums[i] : prefix[i - 1] * nums[i];
  }
  for (let i = len - 1; i >= 0; i--) {
    suffix[i] = i === len - 1 ? nums[i] : suffix[i + 1] * nums[i];
  }
 
  const res: number[] = [];
  for (let i = 0; i < len; i++) {
    if (i === 0) res.push(suffix[i + 1]);
    else if (i === len - 1) res.push(prefix[i - 1]);
    else res.push(prefix[i - 1] * suffix[i + 1]);
  }
  return res;
}

Correct, O(n) time, O(n) extra space.

Cleaner: exclusive arrays

Make prefix[i] mean “product of everything before i”. Then prefix[0] = 1, the empty product, and the edge cases disappear. Same trick as the leading 0 in Prefix Sum.

function productExceptSelf(nums: number[]): number[] {
  const n = nums.length;
  const prefix = new Array(n).fill(1), suffix = new Array(n).fill(1);
  for (let i = 1; i < n; i++) prefix[i] = prefix[i - 1] * nums[i - 1];
  for (let i = n - 2; i >= 0; i--) suffix[i] = suffix[i + 1] * nums[i + 1];
  return prefix.map((p, i) => p * suffix[i]);
}

Best: O(1) extra space

You don’t need either array. Write the left products straight into the output, then walk back from the right with one variable.

function productExceptSelf(nums: number[]): number[] {
  const n = nums.length, out = new Array(n).fill(1);
  let left = 1;
  for (let i = 0; i < n; i++) {
    out[i] = left;      // product of everything before i
    left *= nums[i];
  }
  let right = 1;
  for (let i = n - 1; i >= 0; i--) {
    out[i] *= right;    // times product of everything after i
    right *= nums[i];
  }
  return out;
}

Trace for [1,2,3,4]:

iafter left passafter right pass
011 × 24 = 24
111 × 12 = 12
222 × 4 = 8
366 × 1 = 6

Order matters in both loops: use the running product first, then multiply nums[i] in. Swap them and you include yourself.

Gotchas A

  1. You avoid division, or you explain why it fails on zeros.
  2. You see the split: “except me” = left × right, built with running products instead of O(n²).
  3. You can drop the extra arrays for the follow-up, and explain why the output array doesn’t count as extra space.
  4. You mention edge cases: zeros, negatives, and that the problem guarantees products fit in a 32-bit int.

Gotchas B

  • Inclusive vs exclusive. Inclusive arrays force i-1 / i+1 edge cases. Exclusive ones start at 1 and need none.
  • -0 in JS. [-1,1,0,-3,3] returns [-0, 0, 9, -0, 0]. -0 === 0, so LeetCode accepts it, but Object.is and some test tools tell them apart.
  • Length 1 would return [undefined] in my first version. The constraints say n ≥ 2, so it doesn’t matter here.
  • Name it suffix, not surfix.

Pattern to remember

“Combine everything except position i” → prefix from the left × suffix from the right, each built once.

  • Prefix Sum: the general pattern, with sums instead of products

Graph View

Backlinks