Subarray Sum Equals K
A subarray sums to k when a previous prefix equals current prefix minus k.
Approach
Track a running prefix sum and a map of how many times each prefix value has occurred. At each index, the number of subarrays ending here summing to k equals the count of prefix value (current − k) seen so far. Seed the map with {0: 1} for subarrays starting at index 0.
Time complexity
O(n)
Space complexity
O(n)
Common mistake
Forgetting the initial {0: 1} entry, which misses subarrays that start at the beginning.
See it run, step by step
Generate an interactive lesson for Subarray Sum Equals K — trace every variable and watch the algorithm execute until it clicks.
Start a lesson on Subarray Sum Equals K