Patternwise

Prefix Sum + Hash Map

Any range sum is a difference of two running totals.

Brute force
O(n²) — sum every subarray
With the pattern
O(n) — one pass with O(1) hash lookups
Extra space
O(n) — the prefix map

In plain English

“Think of a car's odometer. To know how far you drove between two towns, you don't re-drive the road — you subtract the odometer reading at the first town from the reading at the second. If you jot down every reading in a notebook, you can instantly ask, "was there ever a town exactly k miles behind me?"”

Why it's fast

A subarray sum nums[i..j] equals prefix[j+1] - prefix[i]. So "does some subarray ending here sum to k?" becomes "have I seen a prefix equal to current - k?" — a single hash map lookup. Brute force re-adds every range (O(n²)); the map remembers all earlier prefixes so each index is handled in O(1). Unlike sliding window, this works with negative numbers.

Spot it when the problem says…

  • subarray sum equals k
  • count the number of subarrays
  • contains negative numbers
  • range sum query
  • sum divisible by k / multiple of k
  • equal number of 0s and 1s

Visualize

Subarray sum equals k

Count the contiguous subarrays whose sum is exactly k (numbers may be negative).

0
3
1
4
2
-7
3
1
4
3
5
3
6
1
7
-4

small numbers under the cells = prefix

seen (prefix → count)

0: 1
01/26

Seed seen with {0: 1}: "an empty prefix with sum 0 exists". That lets a subarray starting at index 0 count.

pythonline 4
1def subarray_sum(nums, k):2    count = 03    prefix = 04    seen = {0: 1}        # prefix sum -> times seen5    for x in nums:6        prefix += x7        count += seen.get(prefix - k, 0)8        seen[prefix] = seen.get(prefix, 0) + 19    return count

variables

prefix
0
count
0
k
7

How to apply it

  1. 01Keep a running sum cur as you scan left to right.
  2. 02Seed the map with the empty prefix: {0: 1} (for counting) or {0: -1} (for lengths).
  3. 03At each index, look up cur - k (or cur % k) in the map and add/compare.
  4. 04Then record cur in the map — after the lookup, so a subarray can't be empty.

Variations you'll meet

Count subarrays with sum k

The visualizer's example. The map stores how many times each prefix sum has appeared.

python
from collections import defaultdictdef subarray_sum(nums: list[int], k: int) -> int:    seen = defaultdict(int)    seen[0] = 1                 # empty prefix    cur = count = 0    for x in nums:        cur += x        count += seen[cur - k]  # subarrays ending here        seen[cur] += 1    return count

Longest subarray (store first index)

Store the earliest index of each prefix; length is i - first[cur - k]. Contiguous Array maps 0 to -1 so the target becomes sum 0.

python
def find_max_length(nums: list[int]) -> int:    first = {0: -1}    cur = best = 0    for i, x in enumerate(nums):        cur += 1 if x else -1        if cur in first:            best = max(best, i - first[cur])        else:            first[cur] = i      # keep the earliest only    return best

Modulo prefix

Two prefixes with the same remainder mod k bound a subarray divisible by k. Normalize negatives with Python's % (already non-negative).

2-D prefix sums

P[r][c] = sum of the rectangle from (0,0). Any sub-rectangle is 4 lookups with inclusion–exclusion.

Common mistakes

  • Forgetting to seed {0: 1}, which misses subarrays that start at index 0.
  • Inserting cur into the map before the lookup, counting an empty subarray when k = 0.
  • For 'longest', overwriting the first index of a prefix with a later one.
  • Reaching for a sliding window when the array has negatives.
  • Off-by-one in range queries: prefix has length n+1, and sum(i..j) is prefix[j+1] - prefix[i].

Practice ladder

Easy → hard. Tick them off as you go.

0/8 solved
  1. 01Find Pivot Index ↗Easy
  2. 02Range Sum Query - Immutable ↗Easy
  3. 03Subarray Sum Equals K ↗Medium
  4. 04Contiguous Array ↗Medium
  5. 05Continuous Subarray Sum ↗Medium
  6. 06Subarray Sums Divisible by K ↗Medium
  7. 07Count Number of Nice Subarrays ↗Medium
  8. 08Number of Submatrices That Sum to Target ↗Hard

Think you've got it?

Let the AI interviewer throw a Prefix Sum + Hash Map problem at you and grade how you explain it.

Mock interview