Prefix Sum with HashMap

Sliding window fails the moment an array can contain negative numbers: growing the window no longer grows the sum, so “shrink while too big” stops making sense. It also fails when a problem asks you to count subarrays rather than find the best one.

The pattern that handles both is prefix sums plus a hash map. It rests on one identity:

$\text{sum}(i..j) = \text{prefix}[j] - \text{prefix}[i-1]$

Rearranged, a subarray ending at j sums to k exactly when some earlier prefix equals $\text{prefix}[j] - k$. So instead of searching for subarrays, you count prefix values you have already seen — one pass, one dict, $O(n)$.

What you’ll learn

• The prefix-sum identity, and the rearrangement that turns it into a lookup.
• Why the map must be seeded with {0: 1}, and what breaks without it.
• Counting occurrences vs. remembering the earliest index — the two flavours, and which each problem needs.
• The remainder and balance transforms that make this pattern cover far more than plain sums.
• Three real LeetCode problems solved in the browser: 560, 974, 525.

The cue

You are looking at prefix sums + a hash map when…

• “How many subarrays” have some sum property — 560, 974, 930, 1248.
• The array can contain negatives or zeros and a window would be wrong — 560 vs 209.
• The condition is about a sum being divisible by k, or a remainder — 974, 523.
• The condition is a balance — equal counts of two things, which becomes “sum is zero” after mapping one to +1 and the other to -1 — 525, 1ND-style problems.
• The array is a tree path rather than a line — 437 is this exact pattern with backtracking.

Window or prefix sums? The decision that matters

Both patterns answer questions about contiguous subarrays. Pick with two questions:

	Sliding window	Prefix sums + map
Values may be negative	No — invariant breaks	Yes
Asks for longest/shortest	Yes	Possible, but awkward
Asks for a count	Rarely	Yes
Space	$O(1)$	$O(n)$

“Minimum size subarray sum ≥ target, positive values” is a window (LC 209). “Count subarrays summing to exactly k, any values” is prefix sums (LC 560). Reaching for a window on LC 560 is the single most common wrong turn in this area.

The template

Two flavours. Which one you need depends on whether the answer is a count or a length.

prefix_sum_hashmap_template.py

# FLAVOUR 1 -- COUNT subarrays. Map: prefix value -> how many times seen.
def count_subarrays_with_sum(nums, k):
    seen = {0: 1}          # one empty prefix, so subarrays starting at index 0 count
    running = 0
    count = 0
    for x in nums:
        running += x
        count += seen.get(running - k, 0)      # every earlier match is a subarray
        seen[running] = seen.get(running, 0) + 1
    return count
 
 
# FLAVOUR 2 -- LONGEST subarray. Map: prefix value -> EARLIEST index seen.
def longest_subarray_with_sum(nums, k):
    first = {0: -1}        # empty prefix sits "before" index 0
    running = 0
    best = 0
    for i, x in enumerate(nums):
        running += x
        if running - k in first:
            best = max(best, i - first[running - k])
        if running not in first:               # only record the FIRST occurrence
            first[running] = i
    return best
 
 
print(count_subarrays_with_sum([1, 1, 1], 2))          # 2
print(longest_subarray_with_sum([1, -1, 5, -2, 3], 3))  # 4

The two details everything hinges on

1. Seed the map. {0: 1} (count) or {0: -1} (index). Without it, a subarray that starts at index 0 is never counted — its prefix is the target, and there is no earlier prefix of 0 to subtract. Missing this gives answers that are off by exactly the number of valid prefixes.

2. For “longest”, keep only the earliest index. Overwriting with later indices shrinks every candidate. Guard with if running not in first. For “count”, you do the opposite — increment every time.

How it works

Take nums = [3, 4, 7, 2, -3, 1, 4, 2], k = 7:

i	nums[i]	running	running - k	seen before?	count
0	3	3	-4	no	0
1	4	7	0	yes (seed)	1
2	7	14	7	yes	2
3	2	16	9	no	2
4	-3	13	6	no	2
5	1	14	7	yes	3
6	4	18	11	no	3
7	2	20	13	yes	4

Four subarrays: [3,4], [7], [7,2,-3,1], [1,4,2]. Notice the seed firing at i = 1 — that is the subarray starting at index 0, and it is exactly what a missing {0: 1} would lose.

	Time	Space
Brute force over all subarrays	$O(n^2)$	$O(1)$
Prefix sums + hash map	$O(n)$	$O(n)$

Visual intuition

The chips under the row are the map from prefix sum to how many times it has been seen. Watch the sentinel {0: 1} do its work on the very first hit.

arrayA subarray sums to k exactly when two prefix sums differ by kLC 560 · O(n) time and space

102132-33141516

0×1

1def subarray_sum(arr, k):2    seen = {0: 1}      # prefix sum -> how many times seen3    running = count = 04    for v in arr:5        running += v6        count += seen.get(running - k, 0)7        seen[running] = seen.get(running, 0) + 18    return count

k3

setupSeed the map with {0: 1}. That sentinel represents the empty prefix and is what lets a subarray starting at index 0 be counted — forgetting it is the classic off-by-one here.

Play‹›1/9⟲

The array contains a negative number, which is precisely why a sliding window cannot solve this: shrinking from the left could increase the sum, so 'too big, shrink' is unsound. Prefix sums do not care about sign.

Complexity

Approach	Time	Space
Every subarray, summed from scratch	$O(n^3)$	$O(1)$
Every subarray, running sum	$O(n^2)$	$O(1)$
Prefix sum + hash map	$O(n)$	$O(n)$

The $O(n)$ space is unavoidable here and worth naming: the map can hold $n$ distinct prefix sums. That is the trade this pattern makes — memory for a factor of $n$ in time — and it is the answer to “can you do it in $O(1)$ space?” (you cannot, in general).

The variant map

The power of this pattern is that you can transform the array first, turning an unrelated-looking condition into “sum equals a target”.

Variant	The transform	Canonical problem
Sum equals k	None	560 Subarray Sum Equals K
Sum divisible by k	Key on running % k instead of running	974 · 523
Equal count of two symbols	Map one to +1, the other to -1; look for sum 0	525 Contiguous Array
Exactly k odd numbers	Map odd to 1, even to 0; look for sum k	1248 Nice Subarrays
Count on a tree path	Same map, but undo the entry when leaving the node	437 Path Sum III
2D submatrix sums	Fix a row pair, collapse columns to 1D, apply the template	1074

The “equal counts” transform is worth internalising

“Longest subarray with equal numbers of 0s and 1s” looks nothing like a sum problem. Map 0 -> -1 and 1 -> +1; now equal counts means the mapped values sum to zero, and the whole problem is longest_subarray_with_sum(mapped, 0). The same trick handles equal counts of any two categories, and generalises to three-plus categories by keying the map on a tuple of pairwise differences.

Practice — real LeetCode problems

LC 560 — Subarray Sum Equals K · Medium

Problem. Given an integer array nums and an integer k, return the total number of contiguous subarrays whose sum equals k.

Constraints. 1 <= len(nums) <= 2 * 10^4, -1000 <= nums[i] <= 1000, -10^7 <= k <= 10^7. Note the negatives — this is why it is not a sliding window.

Examples. nums = [1,1,1], k = 2 gives 2 · nums = [1,2,3], k = 3 gives 2 · nums = [1,-1,0], k = 0 gives 3

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

A subarray ending at the current index sums to k exactly when some earlier prefix equals running - k. So the number of such subarrays is the number of times running - k has been seen — which is what the map stores.

Time $O(n)$. Space $O(n)$.

Count before you record

count += seen.get(running - k, 0) must come before seen[running] += 1. When k == 0, running - k == running, so recording first would let the current prefix match itself and count a zero-length subarray. Test case [1,-1,0], k = 0 (expected 3) exists to catch this ordering.

Note the answer counts subarrays, so equal prefix values must be tallied, not overwritten — [1,-1,0] reaches prefix 0 three times and each pairing is a distinct valid subarray.

Follow-ups you should expect: “Longest such subarray instead?” — switch to flavour 2, storing earliest indices. “All values positive?” — then a sliding window works and gives $O(1)$ space; say so, it shows you know the trade. “Do it on a binary tree?” — LC 437: same map, but decrement the entry as you unwind so only the current root-to-node path is in scope.

LC 974 — Subarray Sums Divisible by K · Medium

Problem. Return the number of contiguous subarrays whose sum is divisible by k.

Constraints. 1 <= len(nums) <= 3 * 10^4, -10^4 <= nums[i] <= 10^4, 2 <= k <= 10^4.

Examples. nums = [4,5,0,-2,-3,1], k = 5 gives 7 · nums = [5], k = 9 gives 0 · nums = [-1,2,9], k = 2 gives 2

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

$\text{sum}(i..j)$ is divisible by k exactly when $\text{prefix}[j] \equiv \text{prefix}[i-1] \pmod{k}$. So instead of looking up running - k, look up running itself — among prefixes already reduced mod k.

Time $O(n)$. Space $O(k)$ — only k distinct remainders exist, which is tighter than the $O(n)$ of LC 560.

A place Python is quietly kinder than C++ or Java

For negative operands, Python’s % returns a result with the sign of the divisor, so -3 % 5 == 2. In C++ and Java, -3 % 5 == -3, and the same code needs ((x % k) + k) % k to normalise. Test case [-1,2,9] exercises exactly this. Worth saying out loud — it shows you know the language semantics rather than having memorised a snippet.

Follow-ups you should expect: “Is there a subarray of length ≥ 2 whose sum is divisible by k?” — LC 523, same idea plus an index check for the length constraint. “Why is space $O(k)$ not $O(n)$?” — because remainders live in [0, k), so a k-slot list beats a dict here.

LC 525 — Contiguous Array · Medium

Problem. Given a binary array nums, return the length of the longest contiguous subarray with an equal number of 0s and 1s.

Constraints. 1 <= len(nums) <= 10^5, nums[i] is 0 or 1.

Examples. nums = [0,1] gives 2 · nums = [0,1,0] gives 2 · nums = [0,1,1,1,1,1,0,0,0] gives 6 · nums = [1,1,1] gives 0

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Map 0 -> -1 and 1 -> +1. A subarray has equal counts exactly when its mapped sum is 0, i.e. when two prefixes share the same running balance. The longest such subarray for a given balance spans from its earliest occurrence to the current index.

Time $O(n)$. Space $O(n)$.

Earliest index, and the {0: -1} seed

Two details, both worth a test case:

• Never overwrite an existing balance. first[running] = i must be guarded by else / if running not in first, otherwise you always measure from the most recent occurrence and report a shorter answer.
• Seed {0: -1}, not {0: 0}. The empty prefix sits before index 0, so a balanced subarray starting at index 0 has length i - (-1) = i + 1. Seeding with 0 would report one less. On [0,1] that is the difference between the correct 2 and a wrong 1.

[1,1,1] returning 0 is the “no valid subarray” case — the balance never repeats, so best stays at its initial 0.

Follow-ups you should expect: “Equal counts of three symbols?” — key the map on a tuple of differences, e.g. (count_a - count_b, count_b - count_c). “Return the subarray itself?” — also store the index where best was set. “Equal counts of any two values in a non-binary array?” — same idea, one map per pair of interest.

LeetCode problem set

Generated from the problem database, so each entry carries its sheet membership and reported companies. Tick them off as you go — progress is saved in this browser, and the Export button writes it to a file you can keep.

LC 437 is the one that proves you understand the pattern

Path Sum III is LC 560 on a tree. Carry the map down the recursion, and undo your insertion as you return (seen[running] -= 1). Without that undo, prefixes from a sibling branch leak into the current path and inflate the count. It is the cleanest test of whether you understand why the map holds what it holds, rather than having memorised the loop.

8 problems

0 easy7 medium1 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

AllEasyMediumHard

Unsolved onlyExportImportReset

• ○437Path Sum IIImediumThe same map on a **tree path** -- decrement on the way back up
• ○523Continuous Subarray SummediumRemainders plus a "length at least 2" index check
• ○525Contiguous ArraymediumThe `+1 / -1` balance transform; earliest index
• ○560Subarray Sum Equals KmediumThe base counting template; negatives rule out a window
• ○930Binary Subarrays With SummediumCounting with a binary array -- or `atMost(k) - atMost(k-1)`
• ○974Subarray Sums Divisible by KmediumKey on `running % k`; space drops to $O(k)$
• ○1248Count Number of Nice SubarraysmediumMap odd to `1`, even to `0`, then count sum `== k`
• ○1074Number of Submatrices That Sum to TargethardFix a row pair, collapse to 1D, then run LC 560

Dry run

LC 560 with k = 3, nums = [1, 2, 3, -3, 1, 1, 1]. The want column is the whole idea: a subarray ending here sums to k exactly when some earlier prefix equals running − k.

i	v	running	want = running − k	seen count	count	map after
—	—	0	—	—	0	{0: 1}
0	1	1	−2	0	0	{0:1, 1:1}
1	2	3	0	1	1	{0:1, 1:1, 3:1}
2	3	6	3	1	2	{0:1, 1:1, 3:1, 6:1}
3	−3	3	0	1	3	{0:1, 1:1, 3:2, 6:1}
4	1	4	1	1	4	{0:1, 1:1, 3:2, 4:1, 6:1}
5	1	5	2	0	4	… 5:1
6	1	6	3	2	6	… 6:2

Answer: 6 subarrays.

Three things that table makes concrete:

• The {0: 1} sentinel earns its keep at i = 1. The subarray [1, 2] starts at index 0, so the “earlier prefix” it needs is the empty prefix. Omit the sentinel and every subarray starting at index 0 is missed — the single most common bug in this pattern.
• At i = 3 the running sum returns to 3, a value already seen. That is only possible because of the negative number, and it is exactly why the map counts occurrences rather than storing a boolean.
• At i = 6, want = 3 has been seen twice, so the count jumps by 2. Using a set instead of a counter would add 1 and silently undercount.

Order matters: look up before you insert

count += seen[running - k] must happen before seen[running] += 1. With k = 0 the two are the same key, and inserting first counts the current prefix against itself — producing a phantom empty subarray at every index.

Interview follow-ups

They ask	What they’re checking	The answer
“Why not a sliding window?”	Whether you know each pattern’s limits	Negative values break the window’s monotonic sum; and windows find extremes, not counts
“Why seed with {0: 1}?”	Whether you derived it or copied it	It represents the empty prefix, so subarrays starting at index 0 are counted
“Count vs. earliest index?”	Whether you match the map to the question	Counting a total means tally every occurrence; measuring a length means keep only the first
“What if all values are positive?”	Trade-off awareness	A window then works and needs $O(1)$ space instead of $O(n)$
“Space is $O(n)$ — can you do better?”	Precision	For the divisibility variant, yes: $O(k)$, since only k remainders exist
“Extend to 2D”	Composition	Fix a pair of rows, collapse each column into a running sum, and run the 1D template — $O(rows^2 \cdot cols)$

Edge-case checklist

• k = 0 — forces the count-before-record ordering; [1,-1,0] is the test.
• Negative numbers — the entire reason for this pattern; make sure nothing in your solution assumes monotonicity.
• Zeros in the array — create repeated prefix values and therefore extra valid subarrays; they must be tallied, not deduplicated.
• Whole array is the answer — verifies the seed entry works.
• No valid subarray — must return 0, not -1 or float("inf").
• Single element — [5], k = 5 gives 1; [5], k = 9 gives 0.
• Overflow — irrelevant in Python (arbitrary-precision ints), but worth naming if the interviewer thinks in C++ or Java.
• Earliest-index guard (length variants) — never overwrite a balance already in the map.

Self-check

pch.quizTag Prefix sum with a hash map — self-check

1. Why is the map seeded with {0: 1}?

   A To avoid a KeyError on the first lookup B It represents the empty prefix, which is what a subarray starting at index 0 needs to match against C Because prefix sums are always non-negative D It is an optimisation and can be omitted
   pch.quizShowAnswer

   B — It represents the empty prefix, which is what a subarray starting at index 0 needs to match against — A subarray from index 0 to i has sum running[i] − running[-1], and running[-1] is the empty prefix, 0. Without the sentinel every such subarray is missed — and the bug is invisible on inputs whose answers all start later.

2. The array contains negative numbers. Why does that rule out a sliding window?

   A Windows cannot hold negative values B Shrinking from the left could increase the sum, so the 'too big → shrink' decision is no longer sound C The sum would overflow D It does not — a window works fine
   pch.quizShowAnswer

   B — Shrinking from the left could increase the sum, so the 'too big → shrink' decision is no longer sound — The window pattern needs the sum to move monotonically as the window grows and shrinks. A negative at the left edge breaks that, and the algorithm silently returns wrong answers. Prefix sums are sign-agnostic, which is exactly why they are the fallback.

3. Why does the map count occurrences instead of storing a set of seen sums?

   A Sets are slower in Python B The same prefix sum can occur several times, and each occurrence is a distinct valid subarray to count C To detect duplicates in the input D It makes no difference for the answer
   pch.quizShowAnswer

   B — The same prefix sum can occur several times, and each occurrence is a distinct valid subarray to count — With negatives the running sum can revisit a value. If prefix p occurred three times, there are three distinct subarrays ending here that sum to k. A set would add 1 and undercount.

4. Does the lookup happen before or after inserting the current prefix sum, and why?

   A After, so the current prefix is available B Before — otherwise with k = 0 the current prefix matches itself and counts a phantom empty subarray C Either order works D Before, purely for speed
   pch.quizShowAnswer

   B — Before — otherwise with k = 0 the current prefix matches itself and counts a phantom empty subarray — The k = 0 case is what exposes it: running − 0 == running, so inserting first makes every index count itself. Lookup, then insert.

5. Same problem but you need the LONGEST subarray summing to k, not the count. What changes?

   A Nothing — the count already gives the length B Store the FIRST index at which each prefix sum occurred, and do not overwrite it C Sort the prefix sums D Switch to a sliding window
   pch.quizShowAnswer

   B — Store the FIRST index at which each prefix sum occurred, and do not overwrite it — For a longest span you want the earliest possible start, so the first occurrence is the useful one — overwriting on a repeat would shorten the answer. That is LC 325, and the not-overwriting detail is the entire difficulty.

Recall card

• Cue — count or measure contiguous subarrays with a target sum, and negatives are possible (which rules out a sliding window).
• Key identity — sum(i..j) == running[j] − running[i-1]. So a subarray ending at j sums to k exactly when some earlier prefix equals running[j] − k.
• Template — seen = {0: 1}; per element: running += v; count += seen.get(running - k, 0); then seen[running] += 1.
• Complexity — $O(n)$ time, $O(n)$ space. The space is unavoidable.
• Remember — the {0: 1} sentinel; count occurrences, do not use a set; look up before inserting.
• Variants — longest instead of count (store the first index); divisible by k (key on running % k); equal 0s and 1s (map 0 → −1 and look for sum 0).

Recap

• $\text{sum}(i..j) = \text{prefix}[j] - \text{prefix}[i-1]$, rearranged into a lookup: a subarray ending here hits the target when running - k has been seen before.
• Two flavours: count occurrences ({0: 1}) for “how many”, earliest index ({0: -1}) for “how long”.
• Seed the map, and for length variants never overwrite an existing key.
• Count before recording so k = 0 cannot match a zero-length subarray.
• Transform first, then apply the template: % k for divisibility, +1/-1 for equal counts, odd/even for parity counts. That is what makes one small template cover a dozen problems.
• Choose this over a window whenever values can be negative, or the question asks for a count.

Next: Kadane and Maximum Subarray — the other classic answer to “contiguous subarray with negatives”, when you want the best sum rather than a count.