Prefix Sum Pattern: Template, Hash Map Trick and Worked Problems

The prefix sum pattern precomputes running totals so that the sum of any subarray becomes one subtraction, prefix[right + 1] - prefix[left], in O(1) time. Use it when a problem asks for many range sums, or asks you to count subarrays whose sum equals, or is divisible by, some value, especially when the array can contain negative numbers.

The pattern has two forms. The array form answers range-sum queries. The hash map form stores how often each running total has appeared, which lets you count matching subarrays in one pass. This guide covers both, plus the 2D version and the difference array, with Python code we ran against test cases before publishing.

When to use the prefix sum pattern

• Repeated range queries. "Return the sum of elements between indices left and right," called many times on an array that does not change.
• Count subarrays with a target sum. "How many contiguous subarrays sum to k?" This is the hash map form.
• Divisibility or balance. "Sum divisible by k," "equal number of 0s and 1s," "longest subarray with sum k." All reduce to comparing two prefix values.
• Negative numbers are allowed. This is the tell that separates it from the sliding window. A window only works when growing it always moves the sum in one direction.
• Left side vs right side. "Pivot index," "product of array except self": each answer combines a running value from the left with one from the right.
• Many range updates, read once at the end. That is the difference array, the inverse of a prefix sum.

If every number is positive and the question is "shortest or longest window with sum at least k," the sliding window pattern is usually simpler and uses O(1) space.

The prefix sum template in Python

Use a prefix array that is one longer than the input, with prefix[0] = 0. That leading zero removes every special case for subarrays that start at index 0.

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

def range_sum(prefix, left, right):    # inclusive indices
    return prefix[right + 1] - prefix[left]

Building costs O(n) once; every query after that is O(1). This is the full solution to Range Sum Query - Immutable (LeetCode 303). In Python, itertools.accumulate(nums, initial=0) builds the same array in one line.

The hash map form rests on one identity: the sum of nums[i..j] equals prefix[j + 1] - prefix[i]. So "a subarray ending here sums to k" means "some earlier prefix equals running - k." Count earlier prefixes in a dictionary and you never need the array at all.

Worked problems

1. Subarray Sum Equals K (LeetCode 560, Medium)

Problem: count the contiguous subarrays of nums whose sum is exactly k. Values can be negative, so a sliding window fails. See Subarray Sum Equals K.

Idea: walk left to right with a running total. At each index, every earlier prefix equal to running - k starts a subarray that ends here and sums to k. Seed the map with {0: 1} for the empty prefix, which covers subarrays that start at index 0.

from collections import defaultdict

def subarray_sum(nums, k):
    seen = defaultdict(int)
    seen[0] = 1                        # the empty prefix
    running = count = 0
    for x in nums:
        running += x
        count += seen[running - k]     # earlier prefixes that complete a sum of k
        seen[running] += 1             # add AFTER counting
    return count

Time: O(n). Space: O(n) for the map. The order of the last two lines matters: if you add the current prefix before counting, k = 0 counts an empty subarray.

2. Subarray Sums Divisible by K (LeetCode 974, Medium)

Problem: count the non-empty subarrays whose sum is divisible by k.

Idea: a subarray sum is divisible by k exactly when the two prefix sums around it leave the same remainder. So count remainders instead of raw sums. Any two prefixes with the same remainder form one valid subarray.

def subarrays_div_by_k(nums, k):
    seen = [0] * k                     # seen[r] = prefixes with remainder r
    seen[0] = 1
    running = count = 0
    for x in nums:
        running = (running + x) % k    # Python's % is never negative for k > 0
        count += seen[running]
        seen[running] += 1
    return count

Time: O(n). Space: O(k). In Java, C++ or JavaScript, -1 % 5 is -1, so you must normalize with ((running % k) + k) % k. That one line is the most common bug on this problem.

3. Range Sum Query 2D - Immutable (LeetCode 304, Medium)

Problem: answer many queries for the sum of a rectangle inside a fixed matrix.

Idea: p[r][c] holds the sum of the rectangle from (0, 0) to (r - 1, c - 1). Build it with inclusion-exclusion, then answer each query with four lookups: the big rectangle, minus the strip above, minus the strip to the left, plus the corner you subtracted twice.

class NumMatrix:
    def __init__(self, matrix):
        rows, cols = len(matrix), len(matrix[0])
        self.p = [[0] * (cols + 1) for _ in range(rows + 1)]
        for r in range(rows):
            for c in range(cols):
                self.p[r + 1][c + 1] = (matrix[r][c] + self.p[r][c + 1]
                                        + self.p[r + 1][c] - self.p[r][c])

    def sumRegion(self, r1, c1, r2, c2):
        p = self.p
        return p[r2 + 1][c2 + 1] - p[r1][c2 + 1] - p[r2 + 1][c1] + p[r1][c1]

Time: O(rows × cols) to build, O(1) per query. Space: O(rows × cols).

The difference array: prefix sum in reverse

When a problem applies many "add v to every element from i to j" updates and reads the result once, record each update at its two ends and take one prefix sum at the end. Corporate Flight Bookings (LeetCode 1109, Medium) is the standard example: flights are 1-indexed and each booking adds seats to a range of flights.

def corp_flight_bookings(bookings, n):
    diff = [0] * (n + 1)
    for first, last, seats in bookings:   # flights are 1-indexed
        diff[first - 1] += seats          # range starts here
        diff[last] -= seats               # and stops after flight `last`
    answer, running = [], 0
    for i in range(n):
        running += diff[i]
        answer.append(running)
    return answer

Each update is O(1) instead of O(range length), so the whole thing is O(n + number of bookings).

Prefix sum complexity table

Counting subarrays by brute force is O(n²) with a running sum per start index, so the hash map form is the jump from O(n²) to O(n) that interviewers want to hear you name. The Big-O complexity visualizer shows how large that gap gets as n grows.

Common bugs and edge cases

• Off-by-one indexing. With a length n + 1 array, the sum of nums[l..r] is prefix[r + 1] - prefix[l]. Mixing a length-n prefix with this formula is the most frequent bug.
• Forgetting seen[0] = 1. Without it you miss every subarray that starts at index 0.
• Updating the map before counting. Count first, then record the current prefix.
• Negative remainders in languages other than Python (see LeetCode 974 above).
• Longest vs count. For "longest subarray with sum k," store the first index each prefix appeared at, and never overwrite it. Contiguous Array (LeetCode 525) uses the same idea after mapping 0 to -1.
• Overflow in fixed-width languages. Python integers do not overflow, but in Java or C++ use a 64-bit type for running sums of large values.

Practice list: 10 prefix sum problems

Difficulty labels are LeetCode's own, checked as of October 2026.

Product of Array Except Self uses products instead of sums, but the left-pass and right-pass idea is the same. Prefix maxima show up in Kadane's algorithm too: the maximum subarray sum is the best prefix[j] - min(prefix[i]) for i < j. For more patterns in this family, see the two pointers pattern, the LeetCode patterns guide and the coding interview cheat sheet.

How to practice the prefix sum pattern

Do problems 560, 525 and 974 back to back. They share one idea, and seeing it three times is what makes it automatic. Then explain 560 out loud: why the map starts at {0: 1}, why you count before you insert, and why a sliding window fails with negatives.

CoPilot Interview's Mock Interview can build a coding round from your résumé and the job description and score each spoken answer out of 10 with what to fix and a model answer. The browser AI mock interview needs no install and covers 9 tracks, including coding and SQL.

FAQ

What is the prefix sum pattern?

It is a technique that stores running totals so the sum of any subarray can be computed with one subtraction: prefix[right + 1] minus prefix[left]. A hash map variant counts how often each running total has appeared, which lets you count subarrays with a target sum in one pass.

When should I use prefix sum instead of sliding window?

Use prefix sum when the array can contain negative numbers, when you need many range-sum queries, or when you are counting subarrays with an exact sum or a divisibility rule. Sliding window needs the sum to move in one direction as the window grows, which only holds when all values are non-negative.

Why do we initialize the hash map with {0: 1}?

It represents the empty prefix before index 0. Without it, a subarray that starts at index 0 and sums to k would not be counted, because there would be no earlier prefix equal to running minus k.

What is the time complexity of the prefix sum pattern?

Building a prefix array is O(n) time and O(n) space, and each range query after that is O(1). The hash map version counts subarrays in O(n) average time and O(n) space, compared with O(n squared) for brute force.

What is a difference array?

It is the inverse of a prefix sum. To add a value to a whole range, add it at the start index and subtract it just after the end index. One prefix sum at the end turns those markers into the final array, so each range update costs O(1).

Which LeetCode problems use prefix sums?

Common ones are Range Sum Query - Immutable (303), Subarray Sum Equals K (560), Contiguous Array (525), Continuous Subarray Sum (523), Subarray Sums Divisible by K (974), Range Sum Query 2D - Immutable (304), Find Pivot Index (724), Product of Array Except Self (238) and Corporate Flight Bookings (1109).