Prefix sums and hashing
The sum of a range is the difference of two running totals. Write every running total down as you go, and the position you need is one hash-map lookup away.
Problems worked on this page, and more to practise
- 560. Subarray Sum Equals K
- 525. Contiguous Array
- 862. Shortest Subarray with Sum at Least K
- 303. Range Sum Query - Immutable
- 724. Find Pivot Index
- 1. Two Sum
- 238. Product of Array Except Self
- 974. Subarray Sums Divisible by K
- 523. Continuous Subarray Sum
- 930. Binary Subarrays With Sum
- 1248. Count Number of Nice Subarrays
- 304. Range Sum Query 2D - Immutable
- 1590. Make Sum Divisible by P
When do prefix sums beat a sliding window?
When the numbers can be negative, or when the question asks for an exact target rather than a limit. A window relies on growing making the sum larger and shrinking making it smaller, which a negative number breaks. Prefix sums do not care about direction: the sum of a range is the difference of two running totals whatever the signs are. The cost is O(n) space for the map, where a window needs almost none.
Why does the hash map start with {0: 1} before the loop?
That entry stands for the empty prefix: the running total before any number has joined, which is zero, reached exactly once. A subarray that starts at index 0 needs that entry as its partner, because the total before it started is the total of nothing. Leave the seed out and every answer that begins at the first element goes uncounted. In the index-keeping variant the same entry is written {0: -1}, because index -1 is the position before the array.
Why must the lookup come before inserting the current total?
Because the current total is the end of the range, not a candidate start. If you file it first and then look it up, a range can be paired with itself, which means counting a subarray of length zero. With a non-zero target the mistake usually hides, since the entry you just filed is not the one you ask for. With a target of zero it fires on every step and the count comes out far too high.
What does the map hold, a count or an index?
It depends on the question. Counting subarrays means the map holds how many times each total has been reached, and every one of those earlier positions is a separate answer. Asking for the longest span means the map holds the earliest index each total appeared at, because the earliest start gives the longest span, and that entry is written once and never overwritten. Asking for the shortest span with an at-least target needs neither: a hash map cannot answer that, and a monotonic deque takes over.
Do prefix sums work on a 2D grid?
Yes, with the same identity applied twice. Build a table where each cell holds the sum of the rectangle from the origin to it. Any rectangle is then the value at its far corner, minus the strip above it, minus the strip to its left, plus the small corner both strips removed. Range Sum Query 2D is that exercise. The build is O(rows x cols) and every query after it is constant.