Run it
The prefix-sum count against brute force with both operation counts, the missing-seed bug failing on a one-element array, and the sliding window breaking on a negative number.
Why the sliding window fails
A sliding window works when growing it increases the sum and shrinking it decreases the sum — that monotonicity is what makes "too big, shrink from the left" a valid decision.
With negatives, the sum is not monotonic. On [1, -1, 1] with k = 1, a window whose sum is already 1 might still be extendable to another valid window, and a window whose sum is too large might become correct by growing. There is no correct rule for when to move the left pointer.
| Constraint | Technique |
|---|
| All positive, find a subarray with sum k | Sliding window, O(n) |
| All positive, minimum length with sum ≥ k | Sliding window, O(n) |
| Negatives allowed, count subarrays summing to k | Prefix sums plus a hash map |
| Negatives allowed, maximum sum | Kadane's algorithm |
Recognising which of those four you have been asked is most of the work.
Prefix sums and the key identity
Let prefix[i] be the sum of the first i elements. Then the sum of the subarray from index i to j−1 is prefix[j] - prefix[i].
So a subarray ending at j sums to k exactly when:
prefix[j] − prefix[i] = k ⇒ prefix[i] = prefix[j] − k
Which turns the problem into: while scanning, count how many earlier prefix sums equal current - k. A dictionary of prefix-sum frequencies answers that in O(1).
O(n) time and O(n) space.
counts[0] = 1 is the line everything hinges on. It represents the empty prefix, and it is what allows a subarray starting at index 0 to be counted. Without it, [1, 2, 3] with k = 3 finds only [3] and misses the leading [1, 2], because that subarray needs prefix[i] = 0 to exist.
The order also matters: count before inserting. Inserting running first would let a subarray of length zero match when k = 0.
From a difference to a lookup
Let P(i) be the sum of everything up to index i. The subarray from j+1 to i sums to P(i) − P(j), so it equals k exactly when P(j) = P(i) − k.
That converts "search backwards for a matching start" into "have I seen this value before?", which a dictionary answers in O(1). It is the same move as Two Sum — compute the thing you need rather than hunting for it.
Why {0: 1} and not an empty map
The empty prefix has sum 0, and it must be in the map before the loop starts. Otherwise a subarray beginning at index 0 — where running itself already equals k — has no earlier prefix to match against and is never counted.
Seeding with {0: 1} is the single most commonly missed line in this problem, and it fails on the simplest possible input: [k].
Why not a sliding window
A sliding window needs the sum to grow when the window grows, so shrinking from the left is a sound response to overshooting. With negative numbers that monotonicity is gone: extending the window can make the sum smaller, so there is nothing to slide on.
If the question guarantees all-positive values, say so and use the window — O(1) space instead of O(n). Noticing that the constraint changes the right answer is worth as much as the code.
Tracing it
[3, 4, 7, 2, -3, 1, 4, 2] with k = 7:
| num | running | running - k | Found | counts after |
|---|
| — | 0 | — | — | {0:1} |
| 3 | 3 | −4 | 0 | {0:1, 3:1} |
| 4 | 7 | 0 | 1 | {0:1, 3:1, 7:1} |
| 7 | 14 | 7 | 1 | {…, 14:1} |
| 2 | 16 | 9 | 0 | {…, 16:1} |
| −3 | 13 | 6 | 0 | {…, 13:1} |
| 1 | 14 | 7 | 1 | {…, 14:2} |
| 4 | 18 | 11 | 0 | {…, 18:1} |
| 2 | 20 | 13 | 1 | {…, 20:1} |
Total: 4. The 14:2 entry is the reason a count is stored rather than a set — the same prefix sum recurring means several valid starting points, and a set would count only one of them.
The variants
Return a subarray rather than a count. Store the index of each prefix sum instead of its frequency, and return on the first match.
Longest subarray with sum k. Store the earliest index for each prefix sum — if s not in first: first[s] = i — so the span found is maximal.
Subarray sums divisible by k. Key the dictionary on running % k instead of running. Watch for Python's % returning non-negative results for negative operands, which is actually convenient here; in languages where it does not, normalise with ((r % k) + k) % k.
Binary subarrays with sum k, or "at most k" problems — these are usually sliding windows again, because the values are non-negative.
Contiguous array with equal 0s and 1s. Map 0 to −1 and find the longest subarray summing to 0 — the same technique with a substitution.
2D version: submatrix sum equals target. Fix a pair of rows, compress the columns between them into a 1D array, and run this algorithm. O(n²m).
Edge cases
| Case | Note |
|---|
| k = 0 | Works; counts[0] = 1 and the count-before-insert order matter most here |
| All zeros, k = 0 | Answer is n(n+1)/2 — every subarray qualifies |
| Empty array | 0 |
| Single element equal to k | 1 |
| No subarray sums to k | 0 |
| All negative | Works — nothing assumes a sign |
| Large sums | Python integers are unbounded; other languages need care about overflow |
[0, 0, 0] with k = 0 giving 6 is a good self-check: the dictionary reaches {0: 4} and contributes 1 + 2 + 3.
What it is testing
Do you notice the negatives? Reaching for a sliding window is the expected wrong turn, and identifying why it fails is the insight being probed.
Do you know the prefix-sum identity? sum(i..j) = prefix[j] - prefix[i] is the most reusable formula in array problems.
Do you initialise counts[0] = 1? The single most common bug, and it silently produces answers that are correct except at the start of the array.
Do you count before inserting? Reversing them breaks the k = 0 case.
Do you store counts rather than a set? Repeated prefix sums each contribute a subarray.
Can you adapt it? Longest-subarray and divisible-by-k variants follow from changing what the dictionary stores.
Recap in one screen
- Negative values rule out a sliding window, because the sum is no longer monotonic in the window size.
- Use prefix sums: a subarray ending here sums to k when an earlier prefix equals
running - k. - A dictionary of prefix-sum frequencies answers that in O(1), giving O(n) overall.
- Seed it with
{0: 1} for the empty prefix, or subarrays starting at index 0 are missed. - Count first, then insert — and store frequencies, not a set.