How Do You Find the Number of Subarrays That Sum to K?
Learn the prefix-sum plus hash-map technique to count subarrays summing to k in O(n) time for this common interview question.
Expected Interview Answer
You solve subarray-sum-equals-k in O(n) time by tracking a running prefix sum and a hash map of how many times each prefix sum value has occurred so far, since a subarray from index i+1 to j sums to k exactly when prefix[j] - prefix[i] = k, so at each step you look up how many earlier prefix sums equal prefix[j] - k.
Walking left to right, maintain a running total called the prefix sum, and a hash map that counts how many times each prefix sum value has been seen, seeded with {0: 1} to handle subarrays that start at index 0. At each position, compute the current prefix sum, then check the map for the count of (current prefix sum - k), which tells you exactly how many earlier prefix sums would make a subarray ending here sum to k; add that count to the running answer. Then increment the map’s count for the current prefix sum before moving on, so future positions can reference it. This single pass with O(1) average hash-map operations replaces the naive O(n²) approach of checking every subarray’s sum directly, and it correctly handles negative numbers, unlike a sliding-window approach which only works when all numbers are non-negative.
- O(n) time versus O(n²) for the brute-force nested loop
- O(n) space for the prefix-sum frequency map
- Correctly handles negative numbers, unlike two-pointer sliding window
- The {0: 1} seed cleanly handles subarrays starting at index 0
AI Mentor Explanation
Think of a team’s running total of runs scored ball by ball across an innings as the prefix sum. To find every stretch of consecutive balls that scored exactly k runs, you would ask, at each ball, "was there an earlier running total that is exactly k less than right now?" — because the difference between two running totals is exactly the runs scored in between. A scorer keeps a tally of how many times each running total has occurred so far, so at ball j they instantly know how many earlier moments had a total equal to (current total minus k), each one marking a valid scoring stretch ending here. This turns an O(n²) check of every possible stretch into a single pass through the innings with instant tally lookups.
Step-by-Step Explanation
Step 1
Initialize prefix sum and map
prefix_sum = 0, count_map = {0: 1} to account for subarrays starting at index 0, answer = 0.
Step 2
Walk the array once
For each element, add it to prefix_sum to get the running total.
Step 3
Look up the complement
Add count_map.get(prefix_sum - k, 0) to the answer — that many earlier prefixes make a valid subarray ending here.
Step 4
Record the current prefix sum
Increment count_map[prefix_sum] by 1 before moving to the next element.
What Interviewer Expects
- Derive the prefix-sum-difference insight: subarray(i+1, j) sums to k iff prefix[j] - prefix[i] = k
- Explain why the map is seeded with {0: 1} rather than starting empty
- State the O(n) time and O(n) space complexity, contrasted with O(n²) brute force
- Recognize that a sliding window only works here if all values are non-negative — this problem allows negatives
Common Mistakes
- Forgetting to seed the map with {0: 1}, undercounting subarrays that start at index 0
- Updating the map before doing the lookup, which would incorrectly count the subarray of length 0 or double count
- Assuming a sliding-window/two-pointer approach works here even with negative numbers
- Confusing "sum of subarray" with "sum of contiguous subsequence" versus a non-contiguous subset
Best Answer (HR Friendly)
“I keep a running total as I walk through the array once, and a hash map counting how many times each running total has appeared so far. At each step I check how many earlier running totals are exactly k less than the current one, since that difference tells me a subarray in between sums to k, and I add that count to my answer. It runs in one pass, O(n) time, and correctly handles negative numbers too.”
Code Example
def subarray_sum(nums, k):
count_map = {0: 1}
prefix_sum = 0
answer = 0
for num in nums:
prefix_sum += num
answer += count_map.get(prefix_sum - k, 0)
count_map[prefix_sum] = count_map.get(prefix_sum, 0) + 1
return answer
print(subarray_sum([1, 1, 1], 2)) # 2
print(subarray_sum([1, 2, 3], 3)) # 2
print(subarray_sum([1, -1, 0], 0)) # 3, works with negativesFollow-up Questions
- How would this change if you needed the actual subarrays, not just the count?
- Why doesn’t a sliding window work here if the array can contain negative numbers?
- How would you find the longest subarray summing to k instead of counting all of them?
- How does this prefix-sum technique generalize to 2D subgrid sum problems?
MCQ Practice
1. Why is the count map initialized with {0: 1} before the loop starts?
A prefix sum of exactly k with no prior prefix seen still needs one match — the empty prefix sum of 0 — to count the subarray starting at index 0.
2. What is the time complexity of the prefix-sum hash-map approach to this problem?
A single pass through the array with O(1) average hash-map lookups and inserts gives O(n) overall time.
3. Why can a two-pointer sliding window fail on this problem in general?
A sliding window relies on the window sum monotonically increasing as it expands, which breaks with negative numbers, unlike the prefix-sum approach.
Flash Cards
What is the key prefix-sum insight for this problem? — subarray(i+1, j) sums to k exactly when prefix[j] - prefix[i] = k.
Why seed the count map with {0: 1}? — To correctly count subarrays that start at index 0 of the array.
What is the time complexity of the optimal solution? — O(n), one pass with a hash map of prefix-sum counts.
Does the sliding-window approach work here with negative numbers? — No — sliding window requires non-negative values; use prefix sum + hash map instead.