Prefix Sums — Coding Interview Patterns

Prefix sums are a quiet superpower: a tiny O(n) precomputation that makes every range-sum query O(1), and that combines with hash maps to solve a whole family of subarray problems.

The idea

Build an array prefix where prefix[i] = the sum of the first i elements (so prefix[0] = 0). This takes one O(n) pass. Now the sum of any range [l, r] is just:

sum(l..r) = prefix[r+1] − prefix[l]

An O(1) subtraction — no re-adding the range. If a problem asks many range-sum queries, this turns O(n) per query into O(1) per query after an O(n) setup.

The template

def build_prefix(a):
    prefix = [0] * (len(a) + 1)
    for i, x in enumerate(a):
        prefix[i+1] = prefix[i] + x
    return prefix

p = build_prefix([3,1,4,1,5,9])   # [0,3,4,8,9,14,23]
range_sum = p[5] - p[2]           # sum of indices 2..4 = 13 - 4 = 9

The real power: prefix sum + hash map

The best prefix-sum problems don’t even build the array — they keep a running prefix and a hash map of how many times each prefix value has occurred. A subarray sums to k exactly when running − k was a previous prefix:

def subarray_sum(nums, k):
    count = 0; running = 0
    seen = {0: 1}                          # empty prefix sums to 0
    for n in nums:
        running += n
        count += seen.get(running - k, 0)  # earlier prefixes that make a k-sum
        seen[running] = seen.get(running, 0) + 1
    return count
# subarray_sum([1,1,1], 2) -> 2

This is O(n) time and space, and the same shape solves “subarray sum divisible by k”, “longest subarray with sum k”, and “binary subarrays with sum” — just change what you store.

Worked example: pivot index

Find the index where the sum of everything to the left equals the sum to the right. Prefix sums make this one pass:

def pivot_index(nums):
    total = sum(nums); left = 0
    for i, n in enumerate(nums):
        if left == total - left - n:   # left == right
            return i
        left += n
    return -1
# pivot_index([1,7,3,6,5,6]) -> 3

Step-by-step walkthrough

Trace Subarray Sum Equals K on nums = [1, 2, 1, -1, 2], k = 3. A subarray ending at i sums to k exactly when some earlier prefix sum equals prefix − k, so we count how many times we’ve seen that value.

i	x	prefix	prefix − k	times seen	total	prefix counts before
0	1	1	-2	0	0	{0:1}
1	2	3	0	1	1	{0:1, 1:1}
2	1	4	1	1	2	{0:1, 1:1, 3:1}
3	-1	3	0	1	3	{0:1, 1:1, 3:1, 4:1}
4	2	5	2	0	3	{0:1, 1:1, 3:2, 4:1}

The count is 3 — [1, 2], [2, 1] and [1, 2, 1, -1] — each found with a single map lookup instead of re-summing. The {0: 1} seed is what catches subarrays that start at index 0.

When to reach for it

Signals: the problem involves sums over ranges or subarrays — “sum of range queries”, “subarray sum equals k”, “subarray divisible by k”, “equilibrium/pivot index”, “product of array except self” (prefix products). If you see repeated range aggregation, think prefix sums; if you see “count subarrays with property X”, think prefix + hash map.

Pitfalls

Off-by-one in the indexing. Decide your convention (prefix[0]=0, prefix[i+1]=prefix[i]+a[i], range [l,r] = prefix[r+1]-prefix[l]) and stick to it.
Forgetting the {0:1} seed. In the running-prefix+map version, you must seed the empty prefix (sum 0 seen once), or you’ll miss subarrays that start at index 0.
Overflow in other languages. Prefix sums grow; in Java/C++ use long. (Not an issue in Python.)

Recap

Precompute prefix sums once (O(n)) and every range sum becomes an O(1) subtraction (prefix[r+1]−prefix[l]). Combine a running prefix with a hash map to count subarrays with a target sum in O(n). Signal: range/subarray sums, or count subarrays with property X. The idea extends to 2-D matrices and to prefix products/XOR.

Practice: 10 solved problems on prefix sums → — cover each one, solve it yourself, then check the tested code.

Next: Lesson 8 — Merge Intervals, sort-then-sweep over ranges.