Prefix Sum Pattern: Template + 157 LeetCode Problems

What the prefix sum pattern is

A prefix sum array stores the total of everything before each index, so the sum of any range is the difference of two entries and costs one subtraction no matter how long the range is. Building it is one pass; after that, a thousand range queries are a thousand subtractions instead of a thousand scans. The version that actually shows up in interviews is subtler: to count subarrays whose sum equals k, walk the array keeping the running total and a hash map of how many times each running total has been seen, because a subarray summing to k exists exactly where the current total minus k has appeared before. Seed that map with a zero total seen once, or every subarray that starts at index zero is missed. The same trick generalises past sums — replace the running total with a running parity, a running count difference, or a bitmask of seen characters, and the same map counts subarrays with equal ones and zeros, or with all characters appearing an even number of times.

When to use it

• —Many range-sum queries are made over an array that does not change between them.
• —You are counting subarrays whose sum, parity or balance hits a target.
• —The brute force recomputes the sum of overlapping ranges from scratch.
• —A two-dimensional version is needed: the same idea with inclusion-exclusion over four corners.

The prefix sum template in Python

The shape, not a solution to any one problem. Adapt the condition and the summary being maintained; the skeleton stays the same across the 157 problems listed below.

from collections import defaultdict

def count_subarrays_with_sum(nums, k):
    counts = defaultdict(int)
    counts[0] = 1            # the empty prefix, so a whole prefix can match
    running = 0
    total = 0

    for value in nums:
        running += value
        total += counts[running - k]   # every earlier prefix that closes a window
        counts[running] += 1

    return total

Complexity characteristics

Time

O(n) to build, O(1) per range query

Auxiliary space

O(n)

One pass builds the running totals; after that any range sum is a single subtraction, so k queries cost O(n + k) instead of O(n·k). The hash-map variant that counts subarrays hitting a target sum is a single O(n) pass with an O(n) map. The two-dimensional version costs O(r·c) to build and O(1) per rectangle query, using inclusion–exclusion over four corners.

All 157 prefix sum LeetCode problems

Every problem in the library the prefix sum pattern applies to, grouped by LeetCode's own difficulty rating. 139 of the 157 carry a complete Python solution with a worked example and complexity analysis; the rest are listed for completeness, with the LeetCode Premium ones marked.

Related patterns

Problems sit in more than one pattern more often than not, and the overlap is where the interesting follow-up questions live.

Prefix Sum pattern FAQ

More ways in: all 22 patterns, the curated study lists, or the full problem list.