How do you count subarrays whose sum equals k using a prefix sum and hash map?
Keep a running prefix sum and a map of how many times each prefix sum has occurred. At each step, the number of subarrays ending here with sum k equals the count of earlier prefix sums equal to current minus k.
Explain it simply
Think of your bank passbook balance after each transaction. The money earned between two days is the difference of the two balances. So a stretch of days adds up to k exactly when today's balance minus some earlier balance equals k.
Today you know your balance (the prefix sum). You look up how many earlier days had balance equal to today - k. Each one is a valid starting point. Seed the map with 0 -> 1 so subarrays starting at index 0 count.
Example
function subarraySum(nums, k) {
const seen = new Map([[0, 1]]);
let sum = 0;
let count = 0;
for (const n of nums) {
sum += n;
count += seen.get(sum - k) || 0;
seen.set(sum, (seen.get(sum) || 0) + 1);
}
return count;
}
console.log(subarraySum([1, 2, 3], 3)); // Output: 2
console.log(subarraySum([1, 1, 1], 2)); // Output: 2Complexity
Time O(n), space O(n).
What to say in the interview
"I track a running prefix sum and a map from prefix sum to how often it has appeared. At each element I add the count stored for sum minus k, then record the current sum. This works with negative numbers, unlike a sliding window, and runs in O(n) time with O(n) space."
Common mistakes
- Forgetting to seed the map with 0 -> 1, which misses subarrays that start at index 0.
- Using a sliding window when the array can contain negative numbers.