Pattern 4: Prefix and Suffix
Pay O(n) once to precompute running totals — and then answer questions about any slice of the array in O(1) each.
Try it first: Product of Array Except Self
Before reading the theory, try to solve it. You can start with brute force, you can fail — the point is to feel the problem. The theory comes right below.
Return an array where answer[i] is the product of all elements except nums[i]. Without using division, in O(n).
Example: nums = [1, 2, 3, 4] → [24, 12, 8, 6].
Did you try? Most people think of "total product ÷ nums[i]" — but the statement forbids division (and it would break with zeros). The brute force without division multiplies the other n−1 elements for each i: O(n²). The theory below solves it in O(n) by decomposing "everything except i" into left × right.
The theory: what problem does prefix solve?
Think of an array of sums. How much does it cost to answer "what is the sum of the slice between i and j?". The naive way, O(n) per question — and a problem that asks n questions becomes O(n²).
The waste: each question re-sums elements that were already summed in previous questions. The solution is to accumulate once and reuse forever:
prefix[i] = sum of ALL elements before position i
prefix[0] = 0 (there's nothing before the start)
sum of the slice [i..j] = prefix[j + 1] - prefix[i]
Why does the subtraction work? prefix[j+1] sums everything up to j;
prefix[i] sums everything before i. The difference is exactly the core
[i..j] — any slice, in one subtraction: O(1) per question after O(n) of
preparation.
The signals in the statement
- Repeated questions about sums/products of slices ("range sum").
- "For each position, consider all the rest" — everything to the left × everything to the right.
- "How many subarrays sum to exactly k?" — prefix combined with a hash map.
- Contiguous subarrays with negative numbers (where sliding window broke, remember?).
Prefix + hash map: the combo
Here's the prettiest connection between the lessons. "How many subarrays sum
to k?": every subarray [i..j] with sum k satisfies prefix[j+1] - prefix[i] = k,
that is: prefix[i] = prefix[j+1] - k.
Walk through the array accumulating the sum and ask the hash map: "how many
times have I already seen the prefix current_sum - k?" — it's the Two Sum
template, applied to prefixes! Ask the past, record for the future. O(n) total
for a problem whose brute force is O(n²). (Keep this combo in mind: it'll be
useful soon... 😉)
Example — Product of Array Except Self
"Return an array where answer[i] is the product of all elements,
EXCEPT nums[i] — without using division, in O(n)."
- Brute force: for each i, multiply the other n-1 elements — O(n²).
- The temptation: total product ÷
nums[i]. Besides being forbidden by the statement, division breaks with zeros (division by zero, and with two zeros everything is zero). - The pattern: "everything except i" = (everything to the left of i) × (everything to the right of i). They're exactly a prefix and a suffix of products!
pass 1 (left → right): answer[i] = product of everything before i
pass 2 (right → left): answer[i] *= product of everything after i
Watch the two passes in the visualizer — notice the prefix accumulator
filling answer on the way out, and suffix completing it on the way back:
Why is it O(n)? And why is the space O(1)?
- Time: two passes in sequence — O(n) + O(n) = O(n) (rule 1: sequences add, constants drop).
- Space: the subtle trick — instead of creating arrays
prefix[]andsuffix[](O(n) each), we carry a single scalar accumulator in each pass and write directly intoanswer. Since the answer array doesn't count as extra space (it IS the answer), the extra is two variables: O(1).
| Solution | Time | Extra space | Why |
|---|---|---|---|
| Brute force | O(n²) | O(1) | n products of n-1 factors |
| Division | O(n) | O(1) | ❌ breaks with zeros (and is forbidden) |
| Prefix + suffix arrays | O(n) | O(n) | two auxiliary arrays |
| Accumulators across 2 passes | O(n) | O(1) | writes directly into the answer |
Generalize: prefix isn't only about sums
The running total can be any operation that builds from left to
right: sum, product, maximum ("largest element so far"), count
("how many pairs so far"). You already used one without realizing: the
min_price from the previous lesson was a prefix minimum carried as a
scalar! And the suffix is the same movie back to front.
🧠 Review quiz
0/41. With the prefix array ready, why does the sum of ANY slice [i..j] cost O(1)?
2. In Product Except Self, why doesn't 'total product divided by nums[i]' work?
3. How does the final version of Product Except Self achieve O(1) extra space?
4. 'How many contiguous subarrays sum to exactly k?' (with negatives). What's the O(n) strategy?
Summary
- Prefix = pay O(n) once, answer slices in O(1) forever.
- "Everything except i" = prefix(left) × suffix(right) — two passes.
- Scalar accumulator + writing into the answer = O(1) extra space.
- Prefix + hash map solves counting subarrays with sum k — including with negatives.
Next lesson: the section's last pattern and the most elegant — Kadane, the local decision that solves the maximum subarray in a single pass.