4.4.7 — Product of Array Except Self

LeetCode 238 · Medium · ★ Blind 75

The problem

Return an array where position i holds the product of every element except nums[i].

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

nums   = [-1, 1, 0, -3, 3]
answer = [ 0, 0, 9,  0, 0]

Up to 100,000 elements. No division, and O(n) time. The follow-up asks for O(1) extra space, not counting the output array.

Why division is banned

Without the rule this is two lines: multiply everything, divide by each element. A single zero breaks it, and handling zeros properly needs three branches — no zeros, exactly one zero, two or more zeros.

The solution below has no special case at all. Zeros and negatives flow through the same arithmetic. That is the real reason the rule is there: it is pointing you at the better design, not setting a puzzle.

The pattern

For each position, the answer is everything to its left times everything to its right.

\text{answer}[i] = \left(\prod_{j < i} \text{nums}[j]\right) \times \left(\prod_{j > i} \text{nums}[j]\right)

The brute force recomputes both halves at every index. But the left product for position i+1 is just the left product for position i times one more number. Carrying it in a variable costs nothing.

So: two sweeps in opposite directions, each carrying a running product.

Rows ① and ③ are the same array. The second sweep multiplies into what the first wrote.

The leftmost prefix value is 1, not nums[0]. Nothing sits to the left of position 0, and the product of no numbers is 1. That leading 1 is what makes the boundary work without an if.

The solution

Python

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        answer = [1] * n

        prefix = 1
        for i in range(n):
            answer[i] = prefix          # write BEFORE folding nums[i] in
            prefix *= nums[i]

        suffix = 1
        for i in range(n - 1, -1, -1):
            answer[i] *= suffix         # same discipline, mirrored
            suffix *= nums[i]

        return answer

TypeScript

function productExceptSelf(nums: number[]): number[] {
  const n = nums.length;
  const answer = new Array(n).fill(1);

  let prefix = 1;
  for (let i = 0; i < n; i++) {
    answer[i] = prefix;
    prefix *= nums[i];
  }

  let suffix = 1;
  for (let i = n - 1; i >= 0; i--) {
    answer[i] *= suffix;
    suffix *= nums[i];
  }

  return answer;
}

The order of the two lines inside each loop is the whole trick. When answer[i] = prefix runs, prefix holds the product of everything before i, because nums[i] has not been folded in yet. Swap the lines and every slot includes itself, which is a different and wrong array.

Say the invariant out loud while writing it: prefix is the product of everything strictly before i, and suffix is the product of everything strictly after i. Both loops are then just "use it, then update it".

Trace

nums = [1, 2, 3, 4].

Forward: answer becomes [1, 1, 2, 6] while prefix runs 1 → 1 → 2 → 6 → 24.

Backward, starting with suffix = 1:

i	suffix in	answer[i] becomes	suffix after
3	1	6 × 1 = 6	4
2	4	2 × 4 = 8	12
1	12	1 × 12 = 12	24
0	24	1 × 24 = 24	24

[24, 12, 8, 6].

Why zeros need no branch

Take [1, 0, 3]. The prefix pass gives [1, 1, 0]. The suffix pass multiplies in [0, 3, 1]. Result [0, 3, 0].

Check by hand: excluding index 0 gives 0·3 = 0 ✓, excluding index 1 gives 1·3 = 3 ✓, excluding index 2 gives 1·0 = 0 ✓.

The zero lands in exactly the positions that should see it, and never in the position it came from, because no sweep ever multiplies nums[i] into answer[i]. Two zeros give all zeros for the same reason. Negatives take care of themselves.

Complexity

O(n) time. O(1) extra space, since the output array is excluded by the problem and the only other memory is two scalars.

A version that builds separate prefix[] and suffix[] arrays first is easier to read and is O(n) extra space. That is a fine first answer — then fold them into the output array to meet the follow-up. Showing the improvement is better than starting tight.

Edge cases

Two elements is the minimum input and works. The constraints promise every prefix and suffix product fits in a 32-bit integer, which is worded that way because it is the intermediate running values that could overflow, not the answer. Python and JavaScript cannot hit it here; Java and C++ can.

Where this goes next

• Prefix sums — the same shape with +. 4.2.
• Trapping Rain Water — the water above each position is capped by the tallest bar to its left and to its right. That is this structure with max instead of ×. 4.5.
• Candy — one pass enforces the left rule, one enforces the right, and the answer is the larger of the two.

The rule: when the answer at each position depends on a prefix and a suffix, do two passes in opposite directions and pick the operator to match the question.

What the interviewer will push on

"Why forbid division?" Zeros force three branches; this version needs none.

"O(1) extra space?" Reuse the output array for the prefix pass and keep the suffix in a scalar.

"What if the values were floats?" Division stops being safe even without zeros, because floating-point multiply and divide are not exact inverses. This solution does not care.

"What if the array keeps changing and you must answer many queries?" Precomputed passes are invalidated by every update, so the right structure becomes a segment tree over products — O(\log n) per update and query. Chapter 4.13.4.

One thing to volunteer: state the invariant before writing the loops. That is how you prove the code is right rather than hoping the tests agree.

Next: 4.4.8 Valid Sudoku — back to sets, with the interesting part being how to name a region of a grid with one number.