Hash Maps and Prefix Sums
On this page
Many array questions hide a nested loop: for each element, search the rest for something that fits. This pattern removes the inner loop. You walk the array once and keep a hash map of what you have already seen, so the "search" becomes a single O(1) lookup. Add a running total (a prefix sum) and the same trick answers questions about subarrays, not just pairs.
If you have not read Hash Maps yet, start there: it covers how the map itself works. This page is about using it as a problem-solving pattern.
When to recognise it
- "Find two things that add up to / match / complement each other." The partner of
xistarget − x; ask the map whether you have seen it. - "Count / group by some key." Anagrams, frequencies, first unique character.
- "Subarray whose sum is k", "longest subarray with equal 0s and 1s", "subarray sum divisible by k". The word subarray (contiguous) plus sum points to prefix sums.
- Numbers can be negative. That rules out Sliding Window, whose shrink step assumes adding more never helps, and leaves prefix sums as the standard tool.
- "Answer many range-sum queries on a fixed array." Build the prefix array once; each query is one subtraction.
How it works
Let prefix[i] be the sum of the first i numbers, with prefix[0] = 0. The sum of nums[l..r] is then prefix[r + 1] − prefix[l]. A subarray sum is the difference of two prefix sums.
![Two rows: nums [1, 2, 3, −2, 2] and prefix [0, 1, 3, 6, 4, 6]. The subarray [3, −2] sums to 1, which equals prefix 4 minus prefix 3.](https://storage.ghost.io/c/cc/3d/cc3dd2ec-1125-4515-87dd-11389c0d3c50/content/images/2026/11/000-34c9f27c.png)
So "how many subarrays ending here sum to k?" becomes "how many earlier prefixes equal prefix − k?". Keep a map from prefix value to how many times you have seen it, and that question is one lookup.
Template
from collections import defaultdict
def count_subarrays_with_sum(nums, k):
"""Prefix-sum template: how many contiguous subarrays add up to k."""
seen = defaultdict(int)
seen[0] = 1 # the empty prefix, so subarrays starting at index 0 count
prefix = count = 0
for x in nums:
prefix += x
count += seen[prefix - k] # earlier prefixes that leave exactly k
seen[prefix] += 1 # store AFTER the lookup
return count
Time O(n), space O(n). Two details carry the whole solution: the map starts as {0: 1}, and the lookup happens before the store.
![Step-by-step table for nums [1, 2, 3, −2, 2] with k = 3: at each step the prefix, the value we need (prefix − 3), how many times it was seen, and the map after storing. Total 4.](https://storage.ghost.io/c/cc/3d/cc3dd2ec-1125-4515-87dd-11389c0d3c50/content/images/2026/11/001-8fff9db8.png)
Variants
Store the first index, not a count. For "longest subarray with property P", map each prefix value to the first index where it appeared, and never overwrite it. The classic example turns 0s into −1s, so "equal 0s and 1s" becomes "sum 0":
def longest_balanced(bits):
"""Variant: longest subarray with equal 0s and 1s (store the FIRST index of each prefix)."""
first = {0: -1}
prefix = best = 0
for i, b in enumerate(bits):
prefix += 1 if b == 1 else -1
if prefix in first:
best = max(best, i - first[prefix])
else:
first[prefix] = i
return best
Static range sums. When the array never changes, a plain prefix list answers each query in O(1):
def range_sum_builder(nums):
"""Static range sums in O(1) after O(n) setup: pre[i] = sum(nums[:i])."""
pre = [0]
for x in nums:
pre.append(pre[-1] + x)
return lambda l, r: pre[r + 1] - pre[l] # inclusive l..r
Divisible by k. Store prefix % k instead of prefix: two prefixes with the same remainder bound a subarray whose sum is a multiple of k. In Python % is already non-negative; in Java or C++ add k before taking the remainder again.
Common bugs
- Missing
{0: 1}. Without the empty prefix, subarrays that start at index 0 are never counted. - Storing before looking up. With
k = 0, the current prefix matches itself and you count an empty subarray at every step. - Overwriting the first index in the "longest" variant. Keep the earliest index; a later one can only give a shorter subarray.
- Reaching for a sliding window with negative numbers. The window cannot decide when to shrink. Prefix sums do not care about signs.
- Integer overflow in Java or C++ when sums get large. Use
long.

Say this in the interview
- "A subarray sum is the difference of two prefix sums, so for each end position I need the number of earlier prefixes equal to
prefix − k. A hash map gives me that in O(1), so the whole thing is O(n)." - "I seed the map with prefix 0 seen once, so a subarray that starts at the beginning counts."
- "A sliding window won't work here because the numbers can be negative."
Problems for this pattern
Easiest first:
- Two Sum: the complement lookup in its purest form.
- Valid Anagram: count letters in one string, subtract the other.
- Group Anagrams: group by a computed key.
- Product of Array Except Self: prefix and suffix products, no division.
- Longest Consecutive Sequence: a set answers "is x − 1 here?" so each run is walked once.
- Subarray Sum Equals K: the template above.
- Insert Delete GetRandom O(1): a hash map of value to index plus an array, swap-with-last on delete.
- Logger Rate Limiter: a map from message to the last time it was printed.
- Find Duplicate File in System: group paths by file content as the key.
- Count Primes: a sieve, a boolean table filled in one pass.
Related
Hash Maps (the data structure) · Sliding Window (the alternative when all numbers are non-negative) · Two Pointers (the O(1)-space alternative when the array is sorted) · Pattern Recognition Cheat Sheet