Subarray Sum Equals K
Problem statement
You're given a list of integers nums and a target integer k. Count how
many contiguous stretches of nums (subarrays) add up to exactly k.
nums can contain negative values, so a running total can go down as well
as up — think of it as counting how many time windows in a stream of daily
profit-and-loss numbers, or request-count deltas, net out to exactly a
target change.
Examples
Example 1
Input: nums = [1, 1, 1], k = 2
Output: 2
Explanation: The subarrays [1, 1] (indices 0–1) and [1, 1] (indices
Example 2
Input: nums = [1, 2, 3], k = 3
Output: 2
Explanation: The subarrays [1, 2] (indices 0–1) and [3] (index 2)
Hints
n elements has, and how that grows
as n grows.Approach
Optimal: Prefix sum counted in a hash map
Intuition
The brute force keeps re-deriving "does this subarray sum to k?" one
subarray at a time. Flip the question around: keep a single running total
as you scan left to right, and ask instead, "how many earlier positions had
a running total that was exactly k less than the one I have right now?" —
because the difference between any two running totals is the sum of the
subarray between them. Counting how often each running-total value has
occurred, in a hash map, answers that question in O(1) per element instead
of rescanning.
The map starts with {0: 1} — not empty — because a subarray that starts
at index 0 needs to match against the sum "before anything has been added
yet", which is 0. Without that seed entry, valid subarrays starting right
at the beginning of nums would never be counted.
Steps
- Create a hash map
prefixCountwith one entry:{0: 1}. - Set
curSum = 0andcount = 0. - For each value
xinnums:- Add
xtocurSum. - Let
need = curSum - k. Ifneedis a key inprefixCount, add its count tocount— that many earlier positions form a valid subarray ending here. - Increment
prefixCount[curSum]by 1 (inserting it with count 1 if it wasn't there yet).
- Add
- After the loop, return
count.
Dry run
nums = [1, 1, 1], k = 2. Start with prefixCount = {0: 1}, curSum = 0,
count = 0.
| x | curSum | need = curSum - k | matches found | count after | prefixCount after |
|---|---|---|---|---|---|
| 1 | 1 | -1 | 0 (not in map) | 0 | {0:1, 1:1} |
| 1 | 2 | 0 | 1 (prefixCount[0]) | 1 | {0:1, 1:1, 2:1} |
| 1 | 3 | 1 | 1 (prefixCount[1]) | 2 | {0:1, 1:1, 2:1, 3:1} |
Final count = 2, matching the example — and matching the brute force's
result, but in one pass instead of a double loop.
Edge cases: if k = 0 and nums contains no zero-sum subarray, need
never matches an existing key beyond what's expected, and count stays
correct at 0. Negative numbers are handled without any special case, since
curSum and need are plain integers that can go up or down — nothing here
assumes the running total only increases.
Complexity
Time O(n) - each element is visited exactly once. Looking up and updating a hash map entry are both O(1) on average, so the whole pass costs O(n) instead of the brute force's O(n²). For 20,000 elements that's 20,000 steps instead of roughly 200 million — the difference that actually matters once `nums` gets large.
Space O(n) - the hash map can end up holding one entry per distinct running total seen, which is at most `n + 1` (including the starting `0`).
class Solution:
def subarraySum(self, nums: list[int], k: int) -> int:
prefix_count = {0: 1}
cur_sum = 0
count = 0
for x in nums:
cur_sum += x
need = cur_sum - k
if need in prefix_count:
count += prefix_count[need]
prefix_count[cur_sum] = prefix_count.get(cur_sum, 0) + 1
return count
if __name__ == "__main__":
print(Solution().subarraySum([1, 1, 1], 2)) # 2
print(Solution().subarraySum([1, 2, 3], 3)) # 2RecapThe whole problem in a few lines, for the night before
- Spot it: "count contiguous subarrays that sum to a target k", especially when the array can contain negative numbers
- Idea: track a running sum; keep a hash map counting how often each running-sum value has occurred; for each element, add
prefixCount[curSum - k]to the answer, seeded with{0: 1} - Cost: O(n) time, O(n) space (running-sum brute force: O(n²) time, O(1) space; re-summing from scratch: O(n³))
- Trap: forgetting to seed the map with
{0: 1}silently under-counts every subarray that starts at index 0 - Remember: negative values rule out a sliding window here — the running sum isn't monotonic, which is exactly why the hash-map trick exists
Interview follow-ups
What if you needed the actual subarrays, not just how many there are?
Instead of counting occurrences of each prefix sum, store the list of indices where each prefix sum occurred. When the current running total minus
kmatches a stored prefix sum, every one of those stored indices marks the start of a valid subarray ending at the current position. Time stays O(n) for the scan, but you now also pay for however many subarrays you actually report, and space grows to hold every index instead of just a count.What if
numsonly ever contained non-negative integers — does anything change?The hash-map approach still works exactly as written, and stays O(n). What changes is that a sliding window becomes possible for closely related questions, like "count subarrays whose sum is at most k" or "find the shortest subarray with sum at least k", because with only non-negative values a running sum can only grow as the window's right edge moves and only shrink as the left edge moves — the monotonic behavior a two-pointer window depends on. This exact problem (counting subarrays with sum equal to k) still needs the hash-map trick either way, since "equal to" doesn't shrink or grow monotonically the way "at most" or "at least" does.
The array is a live, unbounded stream — you can't store the whole thing. How would you adapt this?
The hash map of prefix-sum counts can still be kept incrementally, one value at a time, without ever storing the array itself — memory grows with the number of distinct prefix sums seen, not the length of the stream. If that map itself risks growing unbounded over a very long-running stream, the common trade is to expire old entries once you know subarrays older than some window can no longer matter for the query you actually need (e.g., "sum equals k within the last hour"), turning it into a bounded sliding-window variant of the same idea.
Frequently asked questions
Because a running total is compared against "the running total k steps
back", and a subarray that starts at index 0 has nothing before it — its
"before" total is 0. Seeding the map with {0: 1} means that case is
handled the same way as every other position, with no special-cased if i == 0 branch. Try removing it mentally: nums = [2, -2], k = 0 would
under-count, because the subarray [2, -2] (the whole array, matching
against the empty prefix) would never be found.
A sliding window (as in Minimum Size Subarray Sum) relies on the window's
sum changing predictably as you move its edges — usually because all values
are non-negative, so extending the window can only increase the sum, and
shrinking it can only decrease it. Here, nums can contain negative values,
so growing the window doesn't guarantee the sum moves in one direction. That
breaks the assumption a two-pointer window depends on, which is why this
problem reaches for a hash map of prefix sums instead.
Because the improvement isn't in how many subarrays get checked — it's in how much work each check costs. The brute force re-adds every element of a subarray from scratch every time, which is the difference between O(n³) and O(n²) overall. Both the brute force and the "better" approach still examine every one of the n·(n+1)/2 subarrays; the hash-map optimal approach is the one that changes that, by answering "how many subarrays ending here sum to k?" without enumerating subarrays at all.
It's just a running total. prefix[i] is the sum of every element from the
start of the array up through index i - 1. The reason it's useful is that
the sum of any subarray nums[i..j] can be written as prefix[j+1] - prefix[i] — a single subtraction — instead of re-adding every element in
that range each time you want to check it.
Counting how many time windows a cumulative metric returns to a specific value — net requests processed, a budget's running balance, a queue's net enqueue-minus-dequeue count — shows up whenever you're looking for periods where "nothing net changed" or "exactly a target amount changed". The prefix-sum-plus-hash-map pattern is the standard tool for counting that without rescanning the whole series for every window.
