Prefix Sum + Hashmap

A prefix sum turns "sum of a subarray" into "difference of two running totals". Pair it with a hashmap of the totals you've already seen and you can count subarrays with a given sum, remainder or parity in one $O(n)$ pass. This is the prefix state pattern: at index i you stop caring about nums[i] and start caring about the total state from the start to i.

The idea#

Let P[j] be the sum of nums[0..j]. Then the sum of the subarray nums[i..j] is P[j] - P[i-1]. A subarray ending at j sums to k exactly when some earlier prefix equals P[j] - k:

$\text{target} = P_{\text{now}} - P_{\text{old}} \iff P_{\text{old}} = P_{\text{now}} - \text{target}$

If that looks familiar, it should: it's Two Sum on prefixes. As you walk the array, ask the hashmap "how many earlier prefixes had the value I need?" and add that count. Then record the current prefix so later indices can use it.

Every problem in this family follows the same three beats: accumulate → check history → store history. Only the state and the lookup change.

How to spot it#

The prefix sum shows up in more problems than the name suggests, because "sum" can be a count, a remainder or a 0/1 flag. Ask these questions of a new array or string problem.

Range sum queries? Plain prefix sums, no map.
Count subarrays whose sum hits a target? Prefix sum + hashmap of counts.
Divisibility by k? Hashmap of running remainders.
Odd/even or above/below a threshold? Transform each element to 0/1, then count as in 2.
Min or max of the running total? A running sum with a single variable as history.

Each case keeps a different running state and a different kind of history. Here's how they line up:

Question	State (accumulator)	History
Balance point between left and right	Running left sum	Total sum (a constant)
Lowest or highest running total	Running sum	Minimum or maximum so far
Count subarrays with sum `k`	Running sum	Map of `sum -> count`
Count subarrays divisible by `k`	Running remainder	Map of `remainder -> count`
Count subarrays with `k` items of a kind	Running count of that kind	Map of `count -> count`
Longest stretch with a property	Running state	Map of `state -> first index`

Template#

This is the counting version, with the three beats marked. Other members of the family change only the state and the lookup.

seen = map with default 0        # prefix value -> times seen
seen[0] = 1                      # the empty prefix, before index 0
prefix = result = 0
for each x in items:
    prefix += x                  # accumulate
    result += seen[prefix - k]   # check history
    seen[prefix] += 1            # store history
return result

Seeding seen[0] = 1 stands for "the empty prefix". It's what counts subarrays that start at index 0, and it's equivalent to checking if prefix == k: result += 1 inside the loop. Use one or the other, never both.

To see the seed at work, trace nums = [1, 2, 3] with k = 3:

x	prefix	need `prefix - 3`	seen[need]	result	seen after
1	1	-2	0	0	{0: 1, 1: 1}
2	3	0	1	1	{0: 1, 1: 1, 3: 1}
3	6	3	1	2	{0: 1, 1: 1, 3: 1, 6: 1}

The two subarrays are [1, 2] and [3]. The first one is found only because of the seed: at x = 2 the lookup needs prefix 0, which is the empty prefix.

Pitfalls#

These are the mistakes that most often cost a correct answer.

Plain dict with +=. history[state] += 1 on a plain {0: 1} raises KeyError for any new key. Use defaultdict(int) and seed history[0] = 1.
Double-counting the start. The {0: 1} seed and an explicit if prefix == k check do the same job; using both counts those subarrays twice.
Store after you check. Recording the current prefix before the lookup lets a subarray of length zero match when k == 0.
First index, not last. For "longest" or "length at least" questions, store the earliest index per state and don't overwrite it.
Negative remainders. Python's % always returns a value in [0, k) for positive k, but in many other languages -1 % 5 is -1. Normalize with ((x % k) + k) % k there.
Sliding window won't work with negatives. If values can be negative, growing the window doesn't always increase the sum, so a two-pointer window has no valid shrink rule. Prefix + hashmap does not care.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with Subarray Sum Equals K.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Subarray Sum Equals K

This is the template with no twist. Values can be negative, so a sliding window will not work here.

Hint: Subarray Sums Divisible by K

Store prefix % k instead of prefix. If the same remainder comes back, the running sum has gone full circle: the stretch in between added a multiple of k. So add seen[r], then increment it.

Hint: Continuous Subarray Sum

The subarray needs a length of at least 2. Store the first index where each remainder appeared, seeded {0: -1}, and never overwrite it. When remainder r shows up again at i, the length is i - first[r].

Hint: Binary Subarrays With Sum

The values are 0 and 1, so the running sum is a count of 1s. The template works as it is.

Hint: Count Number of Nice Subarrays

Replace odds with 1 and evens with 0. The problem then becomes Binary Subarrays With Sum.

Hint: Pairs of Songs Divisible by 60

This is the pairwise version, so the history is a count per remainder. Under % 60 the multiples of 60 vanish, so (a + b) % 60 == 0 exactly when r_b == (60 - r_a) % 60. For example 20 pairs with 40 and 30 with 30. The outer % 60 turns 60 into 0, so multiples of 60 pair with each other.

Hint: Minimum Value to Get Positive Step by Step Sum

No map is needed. Do not solve the inequalities one by one; track the lowest running sum m instead. The answer is max(1, 1 - m).

Hint: Find the Highest Altitude

This is the same idea with a running maximum. The history is one variable.

Key takeaways#

A subarray sum is a difference of two prefixes, so "count subarrays summing to k" is Two Sum on prefixes.
The loop is always accumulate → check history → store history.
Seed the empty prefix (seen[0] = 1, or {0: -1} for indices) and use defaultdict.
Divisibility means storing remainders; a repeated remainder closes a full circle.
Transform the input (odd → 1) to reduce a new problem to one you already know.

Core idea#

A subarray sum is the difference of two prefix sums. Keep a hashmap of earlier prefixes, and count subarrays with a target sum, remainder or parity in one $O(n)$ pass.

Key points#

A subarray ending now sums to k when an earlier prefix equals prefix - k. That is Two Sum on prefixes.
The loop is always: accumulate, check history, store history.
Seed the empty prefix with seen[0] = 1. It counts subarrays that start at index 0.
Divisible by k: store prefix % k. A repeated remainder means the stretch between added a multiple of k.
Length at least 2 (Continuous Subarray Sum): store the first index per remainder, seeded {0: -1}.
Transform the input: odd to 1, even to 0, then count as usual.
Prefix + hashmap works with negatives. A sliding window does not.

State and history#

Problem	State	History
Range sum queries	prefix array	none
Subarray Sum Equals K	running sum	`sum -> count`
Divisible by K	running remainder	`remainder -> count`
Nice Subarrays	count of odds	`count -> count`
Min Start Value, Highest Altitude	running sum	one min or max

Template#

seen = map with default 0        # prefix value -> times seen
seen[0] = 1                      # the empty prefix
prefix = result = 0
for each x in items:
    prefix += x                  # accumulate
    result += seen[prefix - k]   # check history
    seen[prefix] += 1            # store history
return result

Pitfalls#

Plain dict with +=. A new key raises KeyError. Use defaultdict(int).
Using the {0: 1} seed and an if prefix == k check together. That counts twice.
Storing before checking. A zero-length subarray then matches when k == 0.
Overwriting the first index in "longest" questions. Keep the earliest.
Pair remainders (songs divisible by 60): need (60 - r) % 60, so 0 pairs with 0.

Say it in an interview#

"Count subarrays summing to k is Two Sum on prefix sums."
"Seed the map with the empty prefix so subarrays from index 0 count."