Prefix sum + hashmap

1 min 1 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Given 1, 2, 3, −2, 2 and the target k = 3, count how many contiguous stretches of the list add up to 3. By hand you try every start and every end: 1+2 = 3 yes; 3 alone yes; 3 + (−2) + 2 = 3 yes; 1+2+3−2−1 … and so on. The answer is 3 stretches.

There are about n² ÷ 2 start–end pairs, and adding up each stretch from scratch costs up to n more, so the plain method is O(n³); keeping a running total as the end moves brings it to O(n²). For a list of 100,000 numbers that is still five billion additions.

Build the structure, one piece at a time

Piece one: prefix sums. Let P[j] be the sum of the first j numbers, with P[0] = 0. For our list: P = 0, 1, 3, 6, 4, 6. Now any stretch is a subtraction:

sum of positions i … j − 1 = P[j] − P[i]

Piece two: turn the question around. A stretch ending just before j sums to k exactly when P[i] = P[j] − k for some earlier i. So at each j we need to know: how many earlier prefix sums equal P[j] − k? That is a counting question, and a hash map from prefix value to count answers it in one step.

Walk once, keeping the running prefix and the map. Seed the map with {0: 1}, which stands for the empty prefix before the first element. At each number: update the prefix, look up prefix − k and add its count to the answer, then record the prefix in the map.

The final answer is 4: the stretches 1+2, 3, 3−2+2, and 2+3−2 (positions 1 … 3). The by-hand count missed one, which is exactly why the method is worth having.

Why it is correct

The invariant: when we are at position j, the map holds the count of every prefix P[0] … P[j − 1]. We record each prefix after using it, so this holds. Then the number we add at step j is exactly the number of i < j with P[i] = P[j] − k, which by the subtraction formula is exactly the number of stretches ending at position j − 1 that sum to k. Summing over all j counts every stretch once, grouped by where it ends. Looking up before recording matters: an empty stretch (i = j) sums to 0 and must only count when k = 0, and the seed {0: 1} handles the stretches that start at position 0.

Why it is fast

One pass of n steps, each doing one addition, one lookup and one insert, all about one step: O(n) time, O(n) memory for the map. Five billion additions became a few hundred thousand operations. The gain comes from never re-adding a stretch: the prefix sums store every partial total once, and the map turns "find a matching earlier total" from a scan into a lookup.

How to recognise it in an interview

Cues: "count subarrays whose sum is", "subarray sum divisible by", "equal numbers of 0s and 1s" (map 0 to −1 and look for sum 0), "longest subarray with sum k" (store the first index instead of a count). The first thing to say: "A subarray sum is a difference of two prefix sums, so I will count earlier prefixes equal to current minus k with a hash map."

Subarray Sum Equals K is the example. Subarray Sums Divisible by K keeps prefixes modulo k, because two prefixes with the same remainder differ by a multiple of k. Path Sum III is the same pattern walking down a tree, where the "prefix" is the sum from the root and you remove it from the map when you backtrack.

02The idea in one line

Subarray sum = prefix[j] − prefix[i]; count earlier prefixes worth prefix[j] − k.

Reach for it when: Count/find subarrays with a given sum, divisible sum, or balanced 0/1.

Cost: O(n) time, O(n) space.

03The walk-through, step by step

The video works one example: Subarray Sum Equals K on [1,2,3,-2,2], k=3. These are its captions in order, so you can follow without the video or check a step you missed.

1. sum(i..j) = prefix[j] − prefix[i]: count earlier prefixes equal to prefix[j] − k
2. Seed the map with prefix 0 seen once
3. prefix = 1; need 1 − 3 = -2, seen 0 times
4. Record prefix 1 in the map
5. prefix = 3; need 3 − 3 = 0, seen 1 time
6. Each such prefix is one subarray ending here: count = 1
7. Record prefix 3 in the map
8. prefix = 6; need 6 − 3 = 3, seen 1 time
9. Each such prefix is one subarray ending here: count = 2
10. Record prefix 6 in the map
11. prefix = 4; need 4 − 3 = 1, seen 1 time
12. Each such prefix is one subarray ending here: count = 3
13. Record prefix 4 in the map
14. prefix = 6; need 6 − 3 = 3, seen 1 time
15. Each such prefix is one subarray ending here: count = 4
16. Record prefix 6 in the map
17. Subarrays summing to 3: [1,2], [3], [3,−2,2] → 3
18. One pass with a hash map: O(n) time, O(n) space

04Asked at Google

9 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Prefix Sums: Prefix and suffix products, Difference array (range add), 2D prefix sums.