Prefix Sum + Hash Map

Prefix Sums, lesson 2 of 3

Prefix Sum + Hash Map

Count or measure subarrays with a target sum in one pass, even with negative numbers.

13 min, 0 of 3 activities solved

View cheatsheet

Getting Python ready… examples can run in a moment.

Classic question: how many contiguous subarrays sum to k? Brute force tries every start and end: O(n²) pairs. Prefix sums turn it into a lookup.

A subarray nums[l..r] sums to k exactly when

P[r + 1] - P[l] = k
⟺  P[l] = P[r + 1] - k

So walk left to right keeping a running prefix. At each position ask: how many earlier prefix sums equal prefix - k? Each one marks a start where a subarray ending here sums to k. Keep those counts in a hash map (Counter), and it's O(1) per step.

Example

Dry run: count subarrays summing to k

The three subarrays are [1, 2] (found at i=1), [2, -1, 2] (i=3) and [2, 1] (i=4). We look up before recording the current prefix, so a subarray can never be empty.

Quiz

What does this print?

Why not a sliding window? A window grows while the sum is too small and shrinks while it's too big. That only makes sense when adding an element can't decrease the sum, which means every number must be non-negative. With negatives, a sum that is "too big" can come back down later ([5, -2]), and dropping a negative from the left makes the sum go up, so the window throws away starts that were still useful.

Rule of thumb: all positive → sliding window (O(1) space); negatives or zeros allowed → prefix sum + hash map.

Example

Sliding window vs prefix map, with negatives

Both agree on the positive array. On the second one the window finds nothing, but [1, -1, 5, -2], [5, -2] and [3] all sum to 3. The prefix map gets all three.

Variations of the same trick. What you store in the map changes with the question:

  • count subarrays with sum k → map prefix → how many times seen
  • longest subarray with sum k → map prefix → first index seen (store only the first time, so the subarray is as long as possible), seeded with {0: -1}
  • equal number of 0s and 1s → turn each 0 into −1; now you want the longest subarray with sum 0 (a running "balance")
  • sum divisible by k → two prefixes with the same remainder prefix % k enclose a multiple of k, so key the map on the remainder
Quiz

You need the LONGEST subarray with sum k. The map stores prefix sum → index. When a prefix value appears again, what should you do?

Exercise

Longest subarray with sum k

Write longest_sum_k(nums, k): the length of the longest contiguous subarray whose sum is exactly k, or 0 if there's none. Numbers can be negative.

Use one pass with a dict prefix → first index, seeded with {0: -1}.