1Understand
The idea
Precompute running totals once: prefix[i] is the sum of the first i elements. Then the sum of any range [l, r) is prefix[r], prefix[l], an O(1) subtraction. Combined with a hash map of prefix values already seen, it counts subarrays with a given sum in a single pass, even with negative numbers.
Intuition
A prefix array turns every range-sum question into a subtraction: after building prefix once, sum of [l, r) is prefix[r], prefix[l]. Put a leading 0 so empty prefixes and ranges that start at index 0 work cleanly.
When values can be negative, sliding windows lose monotonicity, but prefix + hash map still counts subarrays with sum k: each running total asks how often running, k has appeared.
The same idea extends to products (careful with zeros), parity, modulo classes, and 2-D grids (inclusion of rectangles).
What you will be able to do
- Build a prefix array with a leading 0
- Combine prefix sums with a hash map
When to use it
- Sum of a subarray or range, many times
- Count subarrays with sum equal to k
- Values can be negative (so a window will not work)
2See it
Walkthrough
Range sum in O(1) after a prefix
nums = [2, 1, 3, 4], prefix[i] = sum of first i elements; range [1, 4) = prefix[4], prefix[1].
1 / 6
Original array. We want sum(nums[1] + nums[2] + nums[3]) = 1+3+4 without rescanning.
Live template
Line 1 active
Complexity: time O(n), space O(n)
Build is O(n); each range query afterward is O(1). The hash-map variant is O(n) time and O(n) space. Prefer a plain prefix array when you answer many static range sums; prefer the map when counting subarrays. Use a Fenwick/segment tree when the array also mutates.
Read the walkthrough as text
Subarray sum equals k. nums = [1, 2, 3], k = 3.
count = {0: 1},running = 0,answer = 0.- See
1: running1. Need1, 3 = −2, absent. Store count of1. - See
2: running3. Need0, present once →answer = 1(subarray[1,2]). Store3. - See
3: running6. Need3, present once →answer = 2(also[3]).
In code:
count = {0: 1}; running = 0; answer = 0for x in nums:running += xanswer += count.get(running - k, 0)count[running] = count.get(running, 0) + 1
3Recognise it
Kinds of problems (7)
Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.
Range sum queries
Example. Many queries: sum of nums[l..r] inclusive.
How. Build prefix with leading 0; each query is prefix[r+1], prefix[l].
Subarray sum equals k (prefix + hash map)
Example. Count subarrays whose sum is k (negatives allowed).
How. Map prefix sum → frequency; at each running sum s, add count[s, k] before updating s.
Product of array except self
Example. Output[i] = product of all nums except nums[i], no division.
How. Prefix products left→right, then a suffix pass right→left multiplying into the answer.
2-D prefix sums
Example. Sum of subrectangle in a matrix, many queries.
How. 2-D prefix: add row above and column left; rectangle sum is four corner prefixes.
Prefix parity / modulo classes
Example. Count subarrays with even sum (mod 2).
How. Track running parity; pairs with same prefix parity give even-length segments between them.
Difference array for range updates (sweep line)
Example. Apply many “add v to [l, r]” updates, then read final array.
How. diff[l] += v, diff[r+1] -= v; prefix-sum diff once to recover values.
Prefix and suffix aggregates (max to the right, penalties)
Example. Best sight or trap rain water precomputes max on each side.
How. One pass builds prefix max; reverse pass builds suffix max; answer uses both at each index.
Common mistakes
Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.
Missing base prefix
Why it happens. The hash map starts empty, so prefixes that start at index 0 are under-counted.
How it fails. Subarray sum k=0 from index 0 alone: without count[0]=1 you never count the prefix itself.
Fix. Seed `count = {0: 1}` (or prefix array with leading 0) before the loop.
Window on negatives
Why it happens. A variable-size sum window assumes adding always helps validity.
How it fails. nums = [1, -1, 0], k=0: shrinking a window cannot recover a positive sum, you miss subarrays.
Fix. Use prefix + hash map for subarray sums when negatives appear; reserve sliding window for nonnegative sums.
Range off by one
Why it happens. Inclusive vs exclusive range endpoints get swapped in prefix[j], prefix[i].
How it fails. Sum of nums[0..2] uses prefix[2]−prefix[0] but you wanted index 0 included, off by one at the left.
Fix. Define prefix[i] as sum of first i elements (exclusive end); range [l,r] is prefix[r+1]−prefix[l].
4Check yourself
Concept check
A short quiz on this lesson before you practise. Optional, and it does not gate coding.
Ready to practise?
Mastery comes from solving. The lesson is optional context.