Subarray Sum Equals K
A subarray sums to k when a previous prefix equals current prefix minus k.
Prefix Sum Trace
Problem
Given an integer array and a target value k, return how many contiguous, non-empty subarrays have sum exactly equal to k. The array may contain positive, zero, or negative values, so the solution must not rely on a sliding window.
Examples
Input: nums = [1, 2, 1, 2], k = 3
Output: 3
Input: nums = [1, -1, 1], k = 0
Output: 1
The Goal
Count the contiguous subarrays of nums whose numbers add up to k.
For [1, 2, 1, 2] and k = 3, there are three: [1, 2], [2, 1] and [1, 2] again, at indices 0 to 1, 1 to 2 and 2 to 3.
Checking every start and end is O(n²). Prefix sums make it one pass.
Count every match
Count each start and end whose numbers add up to k. Numbers can be negative, so a window can't just grow and shrink.
Count matches. Don't stop at the first.
Key Idea: A Subarray Is a Difference of Two Prefix Sums
Let current be the sum of everything up to index i. The subarray from j to i sums to current minus the sum of everything before j.
So the subarrays ending at i that sum to k match the earlier prefix sums equal to current - k. A map frequency counts how often each prefix sum has come up, so one lookup counts all of them.
A subarray's sum is a later prefix sum minus an earlier one.
6 - 3 = 3: the last [1, 2]
The Algorithm
frequency = {0: 1}
current = answer = 0
for x in nums:
current += x
answer += frequency.get(current - k, 0)
frequency[current] = frequency.get(current, 0) + 1
return answerLook up before you record. Recording current first would count an empty subarray whenever k = 0.
| Approach | Time | Space | Negatives? |
|---|---|---|---|
| Prefix sums and a map | O(n) | O(n) | Yes |
| Every start and end | O(n^2) | O(1) | Yes |
| Sliding window | O(n) | O(1) | No |
Walkthrough
Run it on [1, 2, 1, 2] with k = 3.
The running sums are 1, 3, 4 and 6. At 1, frequency has no -2, so nothing counts. At 3, it finds the seed 0: [1, 2]. At 4, it finds 1: [2, 1]. At 6, it finds 3: the last [1, 2].
Each lookup adds one, so the answer is 3. The brackets under nums mark each subarray a lookup finds.
Checkpoint · predict the next step
Step 2 of 14 on the stage: Add nums[0] = 1: current = 1, the sum of everything up to here.
i on 1 (index 0) · frequency = {0: 1} · k 3 · current 1 · answer 0
Pitfalls
- Seed
frequencywith{0: 1}. Without it,[1, 2]withk = 3finds nothing. - Count, don't just mark. A prefix sum can come up more than once, and each time is another subarray.
- Negative numbers break a sliding window, since adding a number can shrink the sum. Prefix sums don't mind.
- With
[0, 0, 0]andk = 0, all 6 subarrays count.
Why does frequency start as {0: 1}?
Complexity
One pass, with one lookup and one update per number, each constant time on average: O(n).
frequency can hold a different sum for every index, so extra space is O(n).
One pass with a prefix-sum map
- Running sumOne add per number.dominantO(n)
- Lookup and recordOn average, per number.O(1)
- frequencyUp to one entry per prefix sum.dominantO(n)
| n | 10 | 100 | 1,000 | 10,000 |
|---|---|---|---|---|
| O(n) | 10 | 100 | 1K | 10K |
One pass, and a map of every prefix sum.
In short
Track a running prefix sum and a map of how many times each prefix value has occurred. At each index, the number of subarrays ending here summing to k equals the count of prefix value (current − k) seen so far. Seed the map with {0: 1} for subarrays starting at index 0.
Common mistake
Forgetting the initial {0: 1} entry, which misses subarrays that start at the beginning.