ASAPUtils
The signal
“How many subarrays sum to k”, with negatives allowed. That second clause is the whole reason this isn’t a window problem — and noticing it is the skill being tested.
Approach ladder
1. Brute force — O(n²)
Every start, extend and accumulate. Correct, too slow at n ≤ 2·10⁴… actually it squeaks by, which
makes it a tempting trap. Aim higher.
2. Why not a sliding window?
A sliding window needs the sum to be monotone: grow when you expand, shrink when you contract. With negative numbers, adding an element can decrease the sum. So “the sum is too big, shrink from the left” is no longer sound — the answer may lie in a longer window. The window silently misses cases.
If the constraints said all values were positive, a window would be the right tool. Read them.
3. The insight
Write down the identity:
sum(l..r) = prefix[r] − prefix[l−1]
Set it equal to k and rearrange:
prefix[r] − prefix[l−1] = k ⟺ prefix[l−1] = prefix[r] − k
So while walking with a running total, the question at each index becomes: how many earlier
prefixes equalled prefix − k? That’s a hash map lookup — the same move as
Two Sum, applied to running totals instead of elements.
4. Optimal — O(n)
int subarraySum(vector<int>& a, int k) {
unordered_map<long long,int> seen{{0, 1}}; // empty prefix
long long prefix = 0;
int count = 0;
for (int x : a) {
prefix += x;
auto it = seen.find(prefix - k);
if (it != seen.end()) count += it->second;
seen[prefix]++;
}
return count;
}
function subarraySum(a, k) {
const seen = new Map([[0, 1]]); // empty prefix
let prefix = 0, count = 0;
for (const x of a) {
prefix += x;
count += seen.get(prefix - k) ?? 0;
seen.set(prefix, (seen.get(prefix) ?? 0) + 1);
}
return count;
}
The two details that decide correctness
The {0: 1} seed. It’s the empty prefix. Without it, a subarray starting at index 0 has no
earlier prefix to subtract and goes uncounted. On nums = [3], k = 3 you’d return 0.
Check before you store. Look up prefix - k first, then record the current prefix. Reverse
them and an element equal to k… well, with k = 0 especially, a value counts itself.
Walkthrough
nums = [1, 2, 3, -2, 2], k = 3:
| i | value | prefix | want (prefix−k) | seen count | total |
|---|---|---|---|---|---|
| — | — | 0 | — | {0:1} | 0 |
| 0 | 1 | 1 | −2 | 0 | 0 |
| 1 | 2 | 3 | 0 | 1 | 1 |
| 2 | 3 | 6 | 3 | 1 | 2 |
| 3 | −2 | 4 | 1 | 1 | 3 |
| 4 | 2 | 6 | 3 | 1 | 4 |
Four subarrays: [1,2], [3], [2,3,-2] and [3,-2,2].
Note [2,3,-2] — it contains a negative and is easy to miss when enumerating by hand, which is
precisely the case a sliding window would also drop. Worth checking against the visualizer.
Complexity
- Time O(n) — one pass.
- Space O(n) — the prefix map.
Traps
- Missing the
{0: 1}seed. The single most common bug in this pattern. - Storing before checking.
- Using a set instead of a count map. Multiple earlier prefixes with the same value each form a distinct subarray.
- Overflow in C++. Use
long longfor the running prefix.
Blank re-solve prompt
Count the subarrays summing to k, with negatives allowed, in O(n). Derive the rearrangement before writing code, and don’t forget the seed.