Coding · Hashing
Subarray Sum Equals K
- Reported in several places
- Medium
- E4 / L4
- 3 sources
Two or more independent public pages, at least one a candidate write-up.
Solve it in the playground, with tests
Given an integer array nums and an integer k, count the contiguous, non-empty subarrays whose elements add up to exactly k. The array can contain negative numbers and zeros. For example, nums = [2,1,-1,1,2] and k = 3 gives 4. The array has up to 100,000 elements.
Restated in our own words, not a quote from Meta or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
I would ask: can the array hold negative numbers or zeros? (Yes, that matters a lot.) Is k allowed to be zero or negative? Do I count subarrays by position, so two equal subarrays at different places count twice? Can the array be empty? How large can n get, and how large can the count be?
Assumptions I would state: contiguous and non-empty subarrays, counted by position, any integer k, an empty array gives 0, n up to 100,000, so the count can reach about 5 billion. That fits exactly in a JavaScript number, but would need a 64-bit integer in Java or C++.
Brute force
Say the obvious answer and why it is too slow.
The direct solution fixes the start of the subarray, extends the end one element at a time while keeping a running sum, and counts every time the sum equals k. That is two nested loops and O(1) work inside, so O(n²) time and O(1) space. It is correct for any input.
The trouble is the size. With n = 100,000 there are about n²/2 = 5 billion subarrays to look at, which takes far too long. A sliding window would be the natural way to avoid this, but it only works when the elements are non-negative: then growing the window can only raise the sum and shrinking it can only lower it. With negatives, extending the window can make the sum go down, so you cannot tell when to move the left edge, and the window method silently loses answers.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- O(n²)
- Time
- O(n) average, Map operations O(1)
- Space
- O(n) distinct prefix sums
The pattern is prefix sums with a hash map of counts. Let P[j] be the sum of the first j elements, with P[0] = 0. The subarray from index i up to j - 1 has sum P[j] - P[i]. We want that to equal k, which means P[i] = P[j] - k.
So walk the array once, keeping the running prefix. At each step, ask: how many earlier prefixes equal (current prefix - k)? Each such earlier prefix is the start of a subarray ending here with sum k. Add that number to the answer. Then record the current prefix in a Map from prefix value to how many times it has been seen.
Three details make it right. First, the map starts with {0: 1}, the empty prefix, so subarrays that begin at index 0 are counted. Second, the lookup happens before the current prefix is inserted, so a subarray is only paired with strictly earlier prefixes. This also stops k = 0 from counting an empty subarray. Third, the map stores counts, not just presence, because several different start positions can share the same prefix value (zeros and negatives make that common), and each one is a separate subarray.
Why does it work with negatives? Nothing here relies on the sums growing. It relies only on subtraction: each subarray corresponds to exactly one pair of prefixes (i, j) with i before j, so each subarray is counted exactly once. Out loud: "Count pairs of prefix sums that differ by k, in one pass with a map."
Walk it through
A dry run on the example, step by step.
| Step | Value | Prefix | Hits (total) | Map after (prefix:count) |
|---|---|---|---|---|
| start | - | 0 | 0 (0) | {0:1} |
| 1 | 2 | 2 | 0 (0) | {0:1,2:1} |
| 2 | 1 | 3 | 1 (1) | {0:1,2:1,3:1} |
| 3 | -1 | 2 | 0 (1) | {0:1,2:2,3:1} |
| 4 | 1 | 3 | 1 (2) | {0:1,2:2,3:2} |
| 5 | 2 | 5 | 2 (4) | {0:1,2:2,3:2,5:1} |
Take nums = [2,1,-1,1,2] and k = 3. The prefix sums are 2, 3, 2, 3, 5, and the map starts as {0:1}.
After 2: prefix 2, we look for -1, nothing. After 1: prefix 3, we look for 0, which is present once (the empty prefix), so the subarray [2,1] counts. After -1: prefix 2, look for -1, nothing. After 1: prefix 3, look for 0, found once, so [2,1,-1,1] counts. After 2: prefix 5, look for 2, which has been seen twice (after the first and third elements), so [1,-1,1,2] and [1,2] count. The total is 4. The table shows the map growing as it goes.
The code
Runnable JavaScript, checked against test cases.
function subarraySum(nums, k) {
const seenCounts = new Map();
seenCounts.set(0, 1);
let prefix = 0;
let total = 0;
for (const value of nums) {
prefix += value;
const needed = prefix - k;
if (seenCounts.has(needed)) {
total += seenCounts.get(needed);
}
seenCounts.set(prefix, (seenCounts.get(prefix) || 0) + 1);
}
return total;
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
Empty array: the loop never runs, so the answer is 0.
- k = 0: with [0,0,0] the answer is 6, because the lookup happens before inserting the current prefix, so only non-empty subarrays are counted.
- Negative numbers: handled, because only subtraction of prefixes is used.
- Negative k: works the same, since the target prefix is just prefix - k.
- Whole array sums to k: found through the seed {0: 1}.
- Repeated prefix values: counts handle them, for example [1,-1,1,-1].
- Large answers: at most n(n+1)/2, exact in a JavaScript number.
Follow-ups to expect
Where the interviewer pushes next.
- How would you return the length of the longest subarray with sum k instead of the count?
- If every number is positive, can you do it with a sliding window and O(1) extra space?
- How would you count subarrays whose sum is divisible by k?
- How does the same idea extend to counting submatrices with a given sum?
- What changes if the numbers arrive as a stream and you must report the count after every element?
Where candidates slip
The mistakes this problem punishes.
The classic slip is reaching for a sliding window or two pointers. It passes examples with only positive numbers and fails once negatives appear.
- Forgetting the seed {0: 1}, which loses every subarray that starts at index 0.
- Inserting the current prefix before the lookup, which counts too many when k = 0.
- Using a Set or a "last index" map, so repeated prefix values are collapsed into one.
- Computing the sum of every pair of positions again, falling back to O(n²).
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.