Prefix and suffix products

36 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Given 1, 2, 3, 4, produce a new list where each position holds the product of all the other numbers: 24, 12, 8, 6. By hand you would multiply the three others for each position: 2·3·4 = 24, 1·3·4 = 12, and so on. That is n − 1 multiplications per position, about n² in total.

The tempting shortcut is to multiply everything once (24) and divide by each number. That fails the moment a 0 appears, and interviewers usually forbid division anyway. So we need a way to get "everything except me" without dividing.

Build the structure, one piece at a time

Split "everything except me" into two halves: everything to my left and everything to my right. The answer at position i is left × right.

Piece one: a prefix product array L, where L[i] is the product of positions 0 … i − 1. It is built left to right by one multiplication per step, and starts at 1 because nothing is to the left of position 0:

Piece two: a suffix product array R, built right to left the same way: R[3] = 1, R[2] = 4, R[1] = 12, R[0] = 24.

Piece three: combine. answer[i] = L[i] × R[i]: 1·24, 1·12, 2·4, 6·1 = 24, 12, 8, 6.

A space saving comes last: write L into the answer array, then sweep from the right with a single running variable for the suffix product and multiply it in as you go. The output array is then the only extra storage.

The same two-sweep shape answers many "both sides" questions. Replace product with sum and you get "find the index where the sum on the left equals the sum on the right" (pivot index). Replace it with maximum and you get the wall heights used in trapping rain water: the water above a bar is bounded by the tallest wall on its left and the tallest on its right.

Why it is correct

The invariant for the left sweep: after step i, L[i] is the product of nums[0 … i − 1]. It holds at i = 0 (empty product is 1), and each step sets L[i] = L[i − 1] × nums[i − 1], which extends the product by exactly one factor. The mirror statement holds for R. Then

L[i] × R[i] = (nums[0] ⋯ nums[i − 1]) × (nums[i + 1] ⋯ nums[n − 1])

which is every factor except nums[i], as required. No division was used, so zeros are harmless: a zero on the left makes L zero from then on, which is the correct answer for every position to its right.

Why it is fast

Three sweeps of n steps, one multiplication each: about 3n operations, O(n) time, against roughly n² for the by-hand method. For 100,000 numbers that is 300,000 multiplications instead of ten billion. Memory is O(1) beyond the output array in the running-variable version.

How to recognise it in an interview

Cues: "except self", "without division", "left side equals right side", "the best pair where one is before the other", or any formula where the value at i depends on an aggregate of everything before i and an aggregate of everything after. Say: "I will precompute a left aggregate and a right aggregate in two sweeps and combine them per position."

Product of Array Except Self is the example. Find Pivot Index uses sums: with the total S and the running left sum l, the right sum is S − l − nums[i], so one sweep suffices. Trapping Rain Water uses left-max and right-max arrays, and the water at i is min(leftMax, rightMax) − height[i].

02The idea in one line

Answer at i = everything to the left × everything to the right.

Reach for it when: 'Product except self', pivot index, best split point, two-sided aggregates.

Cost: O(n) time, O(1) extra with the output array.

03The walk-through, step by step

The video works one example: Product of Array Except Self on [1,2,3,4]. These are its captions in order, so you can follow without the video or check a step you missed.

1. No division: answer[i] = (product on the left) × (product on the right)
2. left[0] = 1: nothing is before index 0
3. left[1] = 1 (product of nums[0..0])
4. left[2] = 2 (product of nums[0..1])
5. left[3] = 6 (product of nums[0..2])
6. right[3] = 1: nothing is after index 3
7. right[2] = 4 (product of nums[3..3])
8. right[1] = 12 (product of nums[2..3])
9. right[0] = 24 (product of nums[1..3])
10. Multiply column-wise: [24, 12, 8, 6]
11. Two passes, and right can be a running scalar: O(n) time, O(1) extra

04Asked at Google

5 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Prefix Sums: Prefix sum + hashmap, Difference array (range add), 2D prefix sums.