Arrays & Strings · Stage 3 of 3
Prefix & Suffix Summaries
Combine left and right passes to answer range or exclusion queries
Foundations
In both lessons so far, one left-to-right pass was enough: the running value and the write boundary depended only on elements you had already seen. What if computing the answer at index i requires knowing both everything to its left and everything to its right?
Those two sides have names. The prefix of index i is every element before it, nums[0] through nums[i - 1], and the suffix is every element after it, nums[i + 1] through the end. A prefix summary is a running value over the prefix, built left to right like the state in the first lesson. A suffix summary is the same idea, built right to left.
On nums = [7, 1, 5, 3, 6], one left-to-right pass records the sum before each index, 0, 7, 8, 13, 16, and one right-to-left pass records the sum after each, 15, 14, 9, 6, 0. Now exclusion questions take O(1): everything except nums[2] = 5 sums to 8 + 9 = 17. So do range questions: nums[1] through nums[3] sum to 16 − 7 = 9, the sum before index 4 minus the sum before index 1.
nums
sum before i
sum after i
Case Scenario
The problem
Product of Array Except Self
Given nums, return an array answer where answer[i] is the product of every element in nums except nums[i].
- Input
- nums = [1, 2, 3, 4]
- Output
- [24, 12, 8, 6]
Product of Array Except Self asks the exclusion question with products instead of sums: answer[i] is the product of the prefix of i times the product of its suffix. For answer[2], that is 1 × 2 from the left times 4 from the right, which is 8. An empty prefix or suffix counts as 1, the product of nothing.
The instinct is to compute each answer from scratch: n - 1 multiplications for every index, O(n²) in total. Dividing the full product by nums[i] looks faster, but the problem forbids division, and it fails the moment nums contains a 0. Two passes of running products avoid both: no division, and no index rescans its neighbors.
Approach 1 · Brute force
Multiply the others for each index
For each index, loop over the whole array and multiply every other value: n - 1 multiplications for each of n indexes.
Time O(n²) · Space O(1)
- 1def productExceptSelf(nums):
- 2 answer = []
- 3 for i in range(len(nums)):
- 4 product = 1
- 5 for j in range(len(nums)):
- 6 if j != i:
- 7 product *= nums[j]
- 8 answer.append(product)
- 9 return answer
Approach 2 · Left pass, then right pass
Walkthrough
Same input, now one step at a time. Each frame highlights the line that runs and the values it changes.
- 1.Fill
answerwith 1s. - 2.Walk forward with
left = 1: storeleftinanswer[i], then multiplyleftbynums[i]. - 3.Walk backward with
right = 1: multiplyanswer[i]byright, then multiplyrightbynums[i]. - 4.Each slot now holds its left product times its right product.
Python
Product of Array Except Self
- Input:
- nums = [1, 2, 3, 4]
- Output:
- [24, 12, 8, 6]
- 1def productExceptSelf(nums):
- 2 n = len(nums)
- 3 answer = [1] * n
- 4 left = 1
- 5 for i in range(n):
- 6 answer[i] = left
- 7 left *= nums[i]
- 8 right = 1
- 9 for i in range(n - 1, -1, -1):
- 10 answer[i] *= right
- 11 right *= nums[i]
- 12 return answer
nums
answer
answer starts as all 1s. 1 is the product of nothing, which is exactly what is left of index 0.
The Pattern
Answer each index from two summaries: the product of everything to its left and the product of everything to its right. A forward pass carries the left product, exactly like the first lesson's running value. A backward pass carries the right product. Each index combines the two in O(1), so no index rescans anything.
From the trace
Product of Array Except Self
nums
answer
Check it against the walkthrough. The forward pass left answer as [1, 1, 2, 6]: answer[2] = 2, the product of 1 × 2 before the 3. The backward pass carried right from 1 to 4, 12, then 24, so answer[2] became 2 × 4 = 8. Neither pass divides, so a 0 in nums needs no special case.
Both earlier lessons are inside this one. The forward pass is the first lesson's running value, written into answer as it goes. The backward pass updates answer in place, so apart from the output, the only extra memory is two numbers: the O(1) space rule from the second lesson.
The summary can be any running value. Sums answered the exclusion and range questions on [7, 1, 5, 3, 6], products answer this problem, and a running maximum from each side tells every index the tallest value to its left and to its right.
Complexity
TimeO(n)
SpaceO(1)
Two passes over n values is O(n) time. Apart from the output array, which the problem does not count, you keep two numbers, so extra space is O(1). The brute force repeats a full pass for every index, which is O(n²).
Brute force
Multiply the others each time
O(n²) time
O(1) space
This technique
Left pass, then right pass
O(n) time
O(1) space
n=100
n=1,000
n=10,000
Multiplications on a log scale. Two passes cost 2n. The brute force costs about n².
When to use this in an interview
- The answer at index
idepends on both sides of it, as in “every element exceptnums[i]”. - Division is banned, or a zero would break a divide-the-total shortcut.
- You must answer many range-sum queries on an array that does not change.
- Half the condition looks left and half looks right, as in “the tallest bar on each side”.
In production
Counters that answer any time range
Monitoring systems such as Prometheus store request counts as cumulative counters: each sample is the running total so far. The number of requests between 10:00 and 10:05 is then one subtraction, the total at 10:05 minus the total at 10:00, instead of a scan over every event in between. A stored running total is a prefix summary, the same idea as the walkthrough's forward pass.
Where this breaks
Two passes answer one fixed question per index. Counting the subarrays that sum to k means looking up earlier prefix sums by value, which needs a hash map, the next lesson's tool.
Your turn
Solve it yourself
You have watched two passes replace a rescan of every index. Write it yourself on Product of Array Except Self, then apply prefix and suffix summaries to Trapping Rain Water and Subarray Sum Equals K, which adds a hash map.
- 1Solve it
Product of Array Except Self
Guided · the problem you traced above
- 2Trapping Rain WaterOn your own · same pattern, no walkthrough
- 3Subarray Sum Equals KOn your own · same pattern, no walkthrough