FAANGPrep Sprint
Subarray Sum Equals K
Count the contiguous subarrays whose sum equals k in one pass, using a running prefix sum and a hash map of the sums seen so far.
Problem Understanding
Count the contiguous, non-empty subarrays of the integer array nums whose elements add up to exactly k.
Strategy (HashMap + Prefix Sum)
We want Sum(i, j) == k.
Since Sum(i, j) = Prefix[j] - Prefix[i-1], we want:Prefix[j] - Prefix[i-1] == k
=> Prefix[i-1] == Prefix[j] - k.
Algorithm:
Iterate through array, maintaining
current_sum.Check HashMap: how many times have we seen
current_sum - kbefore?Add that count to our answer.
Add
current_sumto the HashMap.
Interactive Visualization
K = 2
SEED MAP
nums
0
1
2
sum through i
0
1
2
Sum
0
Sum − k
—
Count
0
Map (sum:times seen)
Subarrays found here
None on this step
Count subarrays summing to 2. The map starts as {0: 1}: the empty prefix, so a subarray can start at index 0
Next
Add nums[0] = 1: running sum 1
Array
Target
Legend & Complexity
The element just added to the running sum
Every element of a subarray found on this step
Map entry: a prefix sum and how many times it has been seen
Time
O(N)
Space
O(N)
Each step adds one number to the running sum and looks up how many earlier prefix sums equal sum - k. Every one of them starts a subarray that ends here; the figure outlines each match.
Edge Cases
Watch out for:
Negative Numbers: Prefix sums are not monotonic! Cannot use Sliding Window (Two Pointers). Must use HashMap.
k = 0: Subarrays with sum 0 are valid.
Zeroes: Multiple zeroes increase count significantly.
Dry Run
Nums: [1, 1, 1], k=2. Map: {0:1}. Count=0. sum=0.
| Num | New Sum | Check (Sum-k) | Map Has Check? | Action | Map Update |
|---|---|---|---|---|---|
| 1 | 1 | 1 - 2 = -1 | No | - | {0:1, 1:1} |
| 1 | 2 | 2 - 2 = 0 | Yes (val=1) | Count += 1 | {0:1, 1:1, 2:1} |
| 1 | 3 | 3 - 2 = 1 | Yes (val=1) | Count += 1 | {0:1, 1:1, 2:1, 3:1} |
Result: 2.
Solution
O(N) Time, O(N) Space.
Subarray Sum Equals K Code
1var subarraySum = function(nums, k) {2 let count = 0;3 let currSum = 0;4 const map = new Map();5 map.set(0, 1);67 for (const num of nums) {8 currSum += num;910 if (map.has(currSum - k)) {11 count += map.get(currSum - k);12 }1314 map.set(currSum, (map.get(currSum) || 0) + 1);15 }16 return count;17};