How many runs were scored between over 11 and over 20? You don't add up ten overs. You look at the scoreboard after over 20, subtract the score after over 10, and you're done. That trick has a name in DSA: prefix sum. With a hash map added, it solves one of the most asked interview questions: subarray sum equals K.
The 12 interview patterns: you are here
- 1Two Pointerssorted + pair
- 2Sliding Windowcontiguous subarray
- 3Prefix Sum + Hash Maprange sums, sum = K
- 4Binary Search on Answersmallest value that works
- 5Fast & Slow Pointerscycle, middle
- 6Merge Intervalsoverlapping ranges
- 7Monotonic Stackcoming soon
- 8Heap / Top-Kcoming soon
- 9Tree Patternscoming soon
- 10Grid BFS & Topological Sortcoming soon
- 11Backtrackingcoming soon
- 12DP Patternscoming soon
Part 1: range sums with a scoreboard
Build the running totals once: start at 0, and keep adding. Now every “sum from here to there” question is one subtraction. Pick any two overs:
🏏 Runs between any two overs, in one subtraction
| Over | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
|---|---|---|---|---|---|---|---|---|---|
| Runs | 4 | 6 | 2 | 8 | 1 | 5 | 12 | 3 | |
| Score after | 0 | 4 | 10 | 12 | 20 | 21 | 26 | 38 | 41 |
Runs in overs 3–5 = score after over 5 (21) − score after over 2 (10) = 11
Build the running total once (O(n)). After that, every range question is one subtraction (O(1)), even if you're asked a million times.
The formula, in code terms: sum(i..j) = prefix[j + 1] − prefix[i]. The + 1 is only because prefix[0] = 0 sits in front, like the score before the first ball.
Part 2: subarray sum equals K (the famous one)
Now the clever bit. Walk through the numbers keeping a running total. If the total now is 20 and K is 7, then any earlier moment when the total was 13 marks the start of a stretch that adds up to 7 (because 20 − 13 = 7). So we keep a hash map of every running total we've seen and how often. Step through it:
🔎 How many subarrays add up to exactly 7?
Add 3 → running total = 3
Need an earlier total of 3 − 7 = -4
Not seen → nothing new
Count so far: 0
Hash map: total → times seen
The question at every step: “Is there an earlier running total that is exactly K less than now?” If yes, the numbers between then and now add up to K. The hash map answers that in O(1).
Four subarrays add up to 7: [3, 4], [7], [7, 2, −3, 1] and [1, 4, 2]. Notice the −3: this works with negative numbers, which sliding window can't handle. (New to hash maps? See hashing explained.)
🔍 Use prefix sum when you see
- ✓Many “sum from i to j” questions on the same array
- ✓Count subarrays with sum exactly K
- ✓Numbers can be negative
- ✓“Equal left and right sums”, “pivot index”
🚫 Don't use it when
- ✗Longest/shortest stretch with a simple rule and positive numbers (sliding window is lighter)
- ✗Pairs from anywhere in a sorted array (two pointers)
- ✗The array keeps changing between questions (needs a Fenwick or segment tree)
The templates
# Range sums
prefix = [0]
for x in nums: prefix.append(prefix[-1] + x)
sum(i..j) = prefix[j + 1] - prefix[i]
# Count subarrays with sum K
seen = {0: 1}; running = count = 0
for x in nums:
running += x
count += seen.get(running - K, 0) # earlier total exactly K less?
seen[running] = seen.get(running, 0) + 1⚡ Memory tricks
- 1
“Scoreboard: big minus small, that's all”
Range sum = later total − earlier total.
- 2
“Start the map at zero: {0: 1}”
So subarrays that start at index 0 get counted.
- 3
“Look back for (total − K)”
That one question is the whole subarray-sum-K solution.
- 4
“Negative numbers? Prefix, not window”
Sliding window can't decide grow vs shrink when numbers can be negative.
Code: range sums and subarray sum = K (Python, Java, C++)
Outputs in the comments come from running the code.
def build_prefix(nums):
"""prefix[i] = sum of the first i numbers (prefix[0] = 0)."""
prefix = [0]
for x in nums:
prefix.append(prefix[-1] + x)
return prefix
def range_sum(prefix, i, j):
"""Sum of nums[i..j] in O(1): total up to j, minus total before i."""
return prefix[j + 1] - prefix[i]
def count_subarrays_with_sum(nums, k):
"""How many contiguous subarrays add up to exactly k?"""
seen = {0: 1} # running total -> how many times we've seen it
running = count = 0
for x in nums:
running += x
count += seen.get(running - k, 0) # an earlier total that is exactly k less
seen[running] = seen.get(running, 0) + 1
return count
runs = [4, 6, 2, 8, 1, 5] # runs scored in each over
prefix = build_prefix(runs)
print(prefix) # [0, 4, 10, 12, 20, 21, 26]
print(range_sum(prefix, 2, 4)) # 11 (overs 3 to 5: 2 + 8 + 1)
print(count_subarrays_with_sum([3, 4, 7, 2, -3, 1, 4, 2], 7)) # 4One pattern, many problems
| Famous problem | How the pattern solves it | Level |
|---|---|---|
| Range Sum Query (Immutable) | Build prefix once, subtract per query | Easy |
| Find Pivot Index | Left sum = prefix, right = total − prefix − x | Easy |
| Subarray Sum Equals K | Hash map of running totals | Medium |
| Continuous Subarray Sum (multiple of k) | Store running total % k | Medium |
| Contiguous Array (equal 0s and 1s) | Treat 0 as −1, find equal totals | Medium |
| Product of Array Except Self | Prefix and suffix products | Medium |
| Range Sum Query 2D | 2D prefix grid | Medium |
🎯 Spot the pattern: is it prefix sum?
In an interview nobody tells you the pattern. Read each problem and decide. Look for the signal words.
1. Answer 10,000 questions of the form “sum of elements from index i to j”.
2. Count the subarrays whose sum is exactly K (numbers can be negative).
3. Find the longest substring without repeating characters.
4. Find the index where the sum on the left equals the sum on the right.
5. Find a pair in a sorted array with sum 20.
🧠 PATH memory card
Remember prefix sum for good
Picture it · Anchor it · Trace it · Hit-recall it. Four quick steps that turn “I read it once” into “I can explain it in an exam”.
- P
Picture it
Your brain remembers scenes far better than definitions.
← swipe to see the whole picture →
The scoreboard says 62 after over 10 and 151 after over 20. Runs in between: 151 − 62 = 89. The scoreboard already did the adding.
- A
Anchor it
A silly sentence you can't forget, where every word maps to the concept.
“Scoreboard: big minus small, and look back for (total − K)”
- Scoreboard→prefix[i] = running total after i items, prefix[0] = 0
- Big minus small→sum(i..j) = prefix[j + 1] − prefix[i]
- Look back→Hash map of totals seen so far, starting {0: 1}
- total − K→If seen c times, c subarrays end here with sum K
- T
Trace it
Run it by hand on a tiny example once. Doing beats reading.
[3, 4, 7, 2, −3, 1, 4, 2], K = 7. Running totals: 3, 7 (7−7=0 seen → 1), 14 (7 seen → 2), 16, 13, 14 (7 seen → 3), 18, 20 (13 seen → 4). Answer 4. - H
Hit-recall it
Test yourself now, then again on the day each card comes back.
Card 1 / 6 · new0 mastered · 0 practisedSay the answer out loud first, then flip and be honest.
Common mistakes
- Forgetting
{0: 1}. You'll miss every subarray that starts at the beginning. - Updating the map before checking. Check for
running − Kfirst, then addrunning, or K = 0 cases go wrong. - Off-by-one in the range formula. Remember the extra 0 at the front:
prefix[j + 1] − prefix[i].
Where to go next
You've learned three array patterns. The next one turns binary search into a superpower: instead of searching a list, you search for the answer itself, like the slowest speed that still finishes on time: binary search on the answer.
Key takeaways
- ✓Prefix sum = running totals, built once in O(n).
- ✓Any range sum = later total − earlier total, in O(1).
- ✓Subarray sum = K: count earlier totals equal to (running − K) with a hash map.
- ✓Start the map with {0: 1}; check before you insert.
- ✓Works with negative numbers, unlike sliding window.
Frequently asked questions
What is a prefix sum in simple words?
A prefix sum array stores running totals: prefix[i] is the sum of the first i numbers. Like a cricket scoreboard that shows the total score after each over, it lets you find the sum of any range by subtracting two totals instead of adding every number again.
What is the formula for a range sum using prefix sums?
With prefix[0] = 0 and prefix[i] = sum of the first i numbers, the sum of nums[i..j] (inclusive, 0-indexed) is prefix[j + 1] − prefix[i]. In words: total up to the end, minus total before the start.
How does prefix sum solve 'subarray sum equals K'?
Walk through the array keeping a running total. A subarray ending here sums to K exactly when some earlier running total equals (current total − K). Store how many times each running total has appeared in a hash map, and add that count at each step. Start the map with {0: 1} for subarrays that begin at index 0.
What is the time complexity of prefix sum?
Building the prefix array takes O(n) time and O(n) space. After that, each range sum query is O(1). Counting subarrays with sum K using a hash map is O(n) time and O(n) space.
When should I use prefix sum instead of sliding window?
Use prefix sum when numbers can be negative, when you must count all subarrays with an exact sum, or when you get many range-sum questions on the same array. Sliding window needs a clear grow/shrink rule, which usually means all numbers are positive.
🧠 Quick check: prefix sum
1. Score after over 10 is 62 and after over 20 is 151. Runs in overs 11 to 20?
2. Why do we start the hash map with {0: 1}?
3. Many range-sum questions on the same array. Best approach?
4. Count subarrays with sum exactly K, array has negative numbers. Which pattern?
Checking your access…