Subarray Sum Equals K
Count the contiguous subarrays that add up to k, with negatives allowed. The standard prefix-sum plus hash map counting trick. Solve it below in Python or JavaScript, then read the walkthrough.
Problem
Given an integer array nums and an integer k, return how many contiguous, non-empty subarrays of nums have a sum equal to k.
Subarrays at different positions count separately, even if they contain the same values. The array can contain negative numbers and zeros.
Example 1
- Input
- nums = [3, 1, 2, 4], k = 3
- Output
- 2
The subarrays [3] and [1, 2] each sum to 3.
Example 2
- Input
- nums = [1, -1, 1, -1], k = 0
- Output
- 4
[1, -1] appears at positions 0–1 and 2–3, [-1, 1] at 1–2, and the whole array also sums to 0.
Example 3
- Input
- nums = [5, 5, 5], k = 10
- Output
- 2
Constraints
- 1 ≤ nums.length ≤ 2 × 10⁴
- -1000 ≤ nums[i] ≤ 1000
- -10⁷ ≤ k ≤ 10⁷
Practice
Runs 12 tests in your browser. Python loads on the first run (about 6 MB, then cached). Press ⌘/Ctrl + Enter to run.
Get asked Subarray Sum Equals K in a real interview?
Interview Solver gives you a working solution live, during your actual coding interview. Invisible to screensharing.
How to solve Subarray Sum Equals K
Pattern: Prefix sums + hash map of counts
Write prefix[j] for the sum of the first j elements. The sum of the subarray from i to j - 1 is prefix[j] - prefix[i]. So "this subarray sums to k" is the same as "some earlier prefix equals prefix[j] - k".
That turns the problem into Two Sum over prefix sums. Walk the array keeping a running total, and keep a map from each prefix value to how many times you've seen it. At each step, add count[total - k] to the answer, then record the current total. Seed the map with {0: 1} for the empty prefix, so subarrays that start at index 0 are counted.
Why not a sliding window? Windows rely on the sum growing when you extend and shrinking when you shrink. With negative numbers that's false, so a window can't know which way to move. Prefix sums don't care about signs.
Approach 1: Brute force over every subarray
For each start i, extend the end j one step at a time while keeping a running sum, and count every time it equals k. No extra memory, but it visits all n(n + 1)/2 subarrays.
Time O(n²) · Space O(1)
Approach 2: Prefix sums with a counting map
- Set
count = {0: 1},total = 0,answer = 0. - For each
xinnums:total += x, thenanswer += count.get(total - k, 0), thencount[total] += 1. - Return
answer.
Looking up before inserting means the current prefix never pairs with itself, so every match is a non-empty subarray.
Time O(n) · Space O(n)
| Approach | Time | Space |
|---|---|---|
| Brute force over every subarray | O(n²) | O(1) |
| Prefix sums with a counting map | O(n) | O(n) |
Solution code
Try the practice editor first. Both solutions pass every test above.
Subarray Sum Equals K solution in Python
def subarray_sum(nums: list[int], k: int) -> int:
count = {0: 1} # prefix sum -> times seen
total = 0
answer = 0
for x in nums:
total += x
answer += count.get(total - k, 0)
count[total] = count.get(total, 0) + 1
return answerSubarray Sum Equals K solution in JavaScript
function subarraySum(nums, k) {
const count = new Map([[0, 1]]); // prefix sum -> times seen
let total = 0;
let answer = 0;
for (const x of nums) {
total += x;
answer += count.get(total - k) ?? 0;
count.set(total, (count.get(total) ?? 0) + 1);
}
return answer;
}Common mistakes
- Forgetting to seed the map with `{0: 1}`, which misses every subarray that starts at index 0.
- Storing whether a prefix was seen instead of how many times, which undercounts when prefixes repeat (zeros, or values that cancel out).
- Inserting the current prefix before the lookup, which counts the empty subarray when k = 0.
- Reaching for a sliding window, which only works when every number is positive.
What interviewers look for
Start with the O(n²) running-sum loop, then point at its inner loop: "for each end, I'm searching for starts whose prefix equals total - k." Once you say that sentence, the hash map is the obvious fix, and the interviewer hears that you got there by reasoning rather than recall.
Explain why a sliding window fails before anyone asks, using a quick example with a negative number. Then trace the map on [1, -1, 1, -1], k = 0, to show the counts (not booleans) matter.
Follow-up questions
What if all numbers are positive?
Then a sliding window works in O(1) extra space: grow the right end, and while the sum exceeds k, shrink from the left. Count each time the sum equals k exactly.
How would you return the length of the longest subarray with sum k?
Store the first index where each prefix value appears instead of a count. At index j, if total - k was seen at index i, the candidate length is j - i. Keeping only the first occurrence maximizes the length.
How would you count subarrays whose sum is divisible by k?
Use the same idea with prefix sums modulo k: two prefixes with the same remainder bound a subarray divisible by k. Count remainders, normalizing negatives to the range 0..k - 1.
Companies that ask Subarray Sum Equals K
Subarray Sum Equals K is tagged by 123 companies in our interview dataset. The score shows how often it comes up at each company.
- PointClickCare100%
- Samcart100%
- Crunchbase100%
- Wolters Kluwer100%
- Paylocity100%
- Ricoh Usa96%
- Credit Karma95%
- And Digital94%
- 23andme94%
- Viasat92%
- Kraken Technologies92%
- Harman International88%
- Meta87.2%
- AMD85.9%
- Coforge85%
- Abbvie85%
- Bandwidth83%
- Revature82%
- Ancestry82%
- 1password81%
- Buffer79%
- Yandex78.5%
- Thg78%
- Accenture77%
and 99 more.
Practice next
Get live help in the real interview
Working solutions in real time during your actual interview. Invisible to screensharing.
Start Free TrialNo credit card required