Sign in to watch this lesson
Algorithms - Arrays · 4:00
Prefix Sums and a Hash Map
Counting subarrays that sum to k, even with negative numbers, in one pass: a subarray sum is the difference of two prefixes, so we sweep the prefixes, look back k in a tally of the ones already seen, and only then insert the new one. We trace it on a small array, cover the pitfalls (the starting zero, look-up order, negative remainders in C++), extend it to divisibility, longest subarrays, balanced windows and XOR, and time it against checking every pair on a Mac.
You will learn
- Rewrite 'subarrays with sum k' as 'pairs of prefixes k apart' and count them in one O(n) sweep with a hash map
- Get the details right: tally[0] = 1 before the sweep, look up before inserting, and normalise negative remainders
- Adapt the sweep to divisibility, longest subarray (first occurrence), balanced +1/-1 windows and XOR targets
- Know when to avoid hashing: small value ranges (use an array) and all-positive inputs (two pointers)