Subarray Sum Equals K
Count the subarrays that add up to a target, even with negative numbers, in O(n) time by storing how often each running total has occurred.
Updated Short read: 5 min read
Approaches at a glance
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n²) | O(1) |
| Running total with a count map | O(n) | O(n) |
The problem
Given an array of integers and a target, return how many subarrays add up to exactly the target. A subarray is a run of one or more consecutive elements. The numbers can be negative or zero.
numbers = [1, 1, 1], target = 2 → 2 ([1, 1] at the start, [1, 1] at the end)
numbers = [1, 2, 3], target = 3 → 2 ([1, 2] and [3])
numbers = [1, -1, 0], target = 0 → 3 ([1, -1], [0] and [1, -1, 0])Two subarrays with the same values at different positions count separately.
Approach 1: brute force
Try every starting position, extending to the right and keeping a running sum.
JavaScript
function subarraySumBruteForce(numbers, target) {
let count = 0;
for (let start = 0; start < numbers.length; start++) {
let sum = 0;
for (let end = start; end < numbers.length; end++) {
sum += numbers[end];
if (sum === target) count++;
}
}
return count;
}Python
def subarray_sum_brute_force(numbers, target):
count = 0
for start in range(len(numbers)):
total = 0
for end in range(start, len(numbers)):
total += numbers[end]
if total == target:
count += 1
return countThere is no break after a match. With negative numbers and zeros around, a longer subarray from the same start can hit the target again.
Time O(n²): every pair of start and end. Space O(1).
Why a sliding window does not work
This looks like a sliding window problem, and for positive numbers it would be. But the window depends on a rule: growing the window raises the sum, shrinking it lowers the sum. A single negative number breaks that rule. When the sum is too large there is no way to know whether to shrink the window or to keep growing it towards a negative number that would bring the sum back down.
Approach 2: running total with a count map
Use prefix sums. Let running be the sum of everything from the start of the array up to the current position. The sum of any subarray is the difference between two running totals:
sum of a subarray = (running total at its end) − (running total just before its start)So a subarray ending at the current position adds up to target exactly when some earlier running total equals running − target. The question "how many subarrays end here?" becomes "how many times has the value running − target appeared as a running total so far?".
A hash map from each running total to the number of times it has occurred answers that in O(1). This is the same move as Two Sum: instead of searching for a partner, work out what the partner must be and look it up.
JavaScript
function subarraySum(numbers, target) {
const seen = new Map([[0, 1]]);
let running = 0;
let count = 0;
for (const value of numbers) {
running += value;
count += seen.get(running - target) ?? 0;
seen.set(running, (seen.get(running) ?? 0) + 1);
}
return count;
}Python
def subarray_sum(numbers, target):
seen = {0: 1}
running = 0
count = 0
for value in numbers:
running += value
count += seen.get(running - target, 0)
seen[running] = seen.get(running, 0) + 1
return countWalkthrough
numbers = [1, -1, 1, 1], target = 1:
| Value | running | Looks up running − 1 | Found | count | Map after |
|---|---|---|---|---|---|
| 0 | 0 → 1 | ||||
| 1 | 1 | 0 | 1 time | 1 | 0 → 1, 1 → 1 |
| -1 | 0 | -1 | 0 times | 1 | 0 → 2, 1 → 1 |
| 1 | 1 | 0 | 2 times | 3 | 0 → 2, 1 → 2 |
| 1 | 2 | 1 | 2 times | 5 | 0 → 2, 1 → 2, 2 → 1 |
The answer is 5. In the fourth row, the running total 0 has occurred twice: once before any element and once after [1, -1]. Each is a different starting point, so two subarrays end at that position: [1, -1, 1] and the single [1].
Time O(n): one pass with constant-time map operations. Space O(n): in the worst case every running total is different.
Why the map starts with 0 → 1
The entry stands for the empty stretch before the first element, whose total is 0. It is what lets a subarray that starts at index 0 be counted.
Take [3] with a target of 3. The running total is 3, and the lookup is for 3 − 3 = 0. Without the starting entry the map is empty, nothing is found and the answer comes out as 0 instead of 1.
Why a map of counts and not a set
A set could only say whether running − target has occurred. That is enough to detect a subarray, but not to count them. Because of negative numbers and zeros, the same running total can occur many times, and each occurrence is a separate starting point. The fourth row of the walkthrough adds 2, not 1.
Try it yourself
Copy a solution from above, add the lines below, and run it. For JavaScript, paste both into the browser console, or save them in a file and run it with node. For Python, save them in a file and run it with python.
JavaScript
console.log(subarraySum([1, 1, 1], 2)); // 2
console.log(subarraySum([1, -1, 1, 1], 1)); // 5Python
print(subarray_sum([1, 1, 1], 2)) # 2
print(subarray_sum([1, -1, 1, 1], 1)) # 5The comment after each line is the result you should see.
Common mistakes
- Leaving out the starting
0 → 1. Every subarray that begins at index 0 is missed. - Storing the running total before looking up. With a target of 0, the lookup would find the entry just added and count an empty subarray. Look up first, then store.
- Using a set. It undercounts whenever a running total repeats.
- Stopping at the first match from a given start in the brute force. Later ends can match as well.
- Trying a sliding window. It gives wrong answers as soon as a negative number appears.
Original problem: LeetCode 560: Subarray Sum Equals K