mediumCodingConceptMidSenior
Count the subarrays whose elements sum to k, where the values may be negative.
Subarray Sum Equals K is solved with prefix sums and a hash map: for each running sum, count earlier prefixes equal to sum-k. This is O(n) time and works with negative numbers, unlike a sliding window. Use this hashing answer to show the decision, trade-off, and evidence rather than a memorised definition.
4 min readUpdated 2026-08-15
Answer
Short answer
Count subarrays summing to k by keeping a running prefix sum and a hash map from prefix-sum value to frequency. At each element, add the count for sum - k before recording the current sum, seed the map with {0: 1}, and use this instead of sliding window when numbers may be negative.
Was this answer helpful?
Likely follow-ups
- Why does the two-pointer window work for this problem when all values are positive, and where exactly does it break otherwise?
- Return the longest such subarray instead of the count. What changes in the map?
- The keys here are boxed integers. What would you need from a custom key class?
- When would you reject a hash map here and prefer sorting or an array?
Related questions
- Group a list of words so that words which are anagrams of each other end up together. What is your key, and what does it cost?mediumAlso on hashing and hash-map5 min
- A cache must evict the least recently used entry and every operation has to be O(1). Which two structures do you need, and why is one of them not enough?mediumAlso on hash-map5 min
- How does HashMap work internally, and what happens when it resizes?mediumAlso on hashing3 min
- Insert, delete and get-a-uniformly-random-member all have to be O(1). What breaks when you delete from the middle?mediumAlso on hash-map6 min