Prefix Sum Pattern: The Template for Range Sum Questions

TL;DR: A prefix sum array stores the running total up to each position. Once you have it, the sum of any range is the difference of two entries, so a question that looked like it needed a loop per query becomes O(1) per query. Pair the same idea with a hash map and you get the second half of the pattern: counting subarrays that sum to a target in one pass, including when the array contains negative numbers, which is exactly where sliding window stops working. Two templates, one identity, and a family of problems that runs from Range Sum Query up to submatrix sums.

This is the ninth deep dive in our pattern series (the full map lives in the hub), following binary search on the answer. Prefix sum is the pattern candidates most often reinvent badly under pressure. Almost everyone can describe the idea when asked directly. Far fewer recognize it inside a question worded as "count the subarrays that ...", and fewer still get the index arithmetic right on the first try. Both of those are learnable in about twenty minutes, which makes this one of the highest return patterns per hour of study.

The tell: how to recognize a prefix sum problem

Suspect this pattern when the question involves totals over contiguous ranges:

• "the sum of the elements between index i and index j"
• "you will be asked many range sum queries" (the repeated-query signal)
• "count the subarrays whose sum equals k"
• "find the subarray with sum k" or "the longest subarray with sum k"
• "the subarray with an equal number of 0s and 1s"
• "the sum of a submatrix" (the 2D version)
• "divisible by k" applied to a subarray sum

The unifying shape: you need many range totals from one fixed array, or you need to find ranges whose total has some property. The brute force recomputes each range with its own loop, which is O(n) per query and O(n²) overall. Prefix sum pays O(n) once and then answers each question in O(1).

The one identity the whole pattern rests on

Here is the sentence that is the pattern: the sum of a range is the difference of two prefixes.

Let P[i] be the sum of the first i elements, so P[0] = 0, P[1] = nums[0], and so on. Then the sum of nums[i..j] inclusive is P[j+1] - P[i]. Everything above the first row of the table is a consequence of that line.

The reason it works is worth saying out loud in an interview, because it is one sentence: P[j+1] counts everything up to and including j, P[i] counts everything before i, and subtracting removes exactly the part you did not ask for. Nothing in that argument depends on the values being positive, which is the property that will matter later.

The template

Build the prefix array with size n + 1 and a leading zero. This is not a stylistic choice, it is what removes the special case for ranges that start at index 0:

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

def range_sum(prefix, i, j):            # sum of nums[i..j], inclusive
    return prefix[j + 1] - prefix[i]

If you instead build a size-n array where prefix[i] includes nums[i], every range sum needs an if i == 0 branch. Candidates who take that route lose time to off-by-one errors on exactly the boundary the interviewer will test. Use n + 1 every time.

The second template: prefix sums plus a hash map

The first template answers questions about ranges you are given. The second answers questions about ranges you have to find, and it is the version that shows up in interviews far more often.

Take "count the subarrays whose sum equals k". A subarray nums[i..j] sums to k exactly when P[j+1] - P[i] = k, which rearranges to P[i] = P[j+1] - k. So as you scan and compute each running total, the number of subarrays ending here equals the number of earlier prefixes equal to running - k. A hash map of prefix counts turns that into a single pass:

def subarray_sum(nums, k):
    counts = {0: 1}                     # the empty prefix has been seen once
    running = 0
    total = 0
    for x in nums:
        running += x
        total += counts.get(running - k, 0)     # close off every match
        counts[running] = counts.get(running, 0) + 1
    return total

The {0: 1} seed is the line candidates forget. It accounts for subarrays that start at index 0: without it, an array whose entire prefix equals k is never counted. If your solution is off by exactly one on inputs like [3], k = 3, this is the cause.

Note the order inside the loop. You read the map before you insert the current prefix. Reversing those two lines lets a zero-length subarray match when k = 0, which is a wrong answer that passes most sample inputs.

The compass: prefix sum or sliding window?

These two patterns cover overlapping territory, and interviewers use the overlap to test whether you understand either one. The rule is short:

• Sliding window needs the running total to move in one direction as the window grows. With non-negative numbers, extending the window can only increase the sum, so shrinking from the left is a valid response to overshooting. That is what makes the window work.
• The moment negative numbers are allowed, that guarantee is gone. Extending a window can now decrease the sum, so there is no rule that tells you when to shrink. Sliding window silently produces wrong answers.
• Prefix sum plus a hash map does not care about signs, because the identity P[j+1] - P[i] never assumed anything about the values.

So: constraints say non-negative and the question asks for a shortest or longest window, use sliding window. Constraints allow negatives, or the question asks you to count qualifying subarrays, use prefix sums. Saying that distinction out loud is worth more than the code, because it shows you chose the tool rather than recognized one problem.

Want the whole family taught in order? The prefix sum chapter of Grokking the Coding Interview builds from Running Sum through Subarray Sum Equals K and 2D range queries with worked traces and code in six languages, then does the same for all 42 patterns (32 common + 10 advanced).

The escalations interviewers actually reach for

• Find Pivot Index: the identity in its simplest form, comparing a left prefix against a right suffix.
• Contiguous Array: find the longest subarray with equal 0s and 1s. Map every 0 to -1 first, and the question becomes "the longest subarray summing to zero", which is the hash map template storing first-seen indices instead of counts. The transformation is the whole problem.
• Continuous Subarray Sum: a subarray sum divisible by k means two prefixes share the same remainder, so store running % k rather than running. The same substitution solves Subarray Sums Divisible by K.
• Product of Array Except Self: the identity applied to products rather than sums, using a prefix pass and a suffix pass so no division is needed. Good evidence that the pattern is about the structure, not about addition.
• Range Sum Query 2D Immutable: build a prefix over the matrix, then read any submatrix with four lookups by inclusion and exclusion. This is where careful index work pays off.
• Difference array (stretch): the inverse construction, where you record changes at range endpoints and take a prefix sum at the end to apply many range updates in O(1) each. Useful for problems like Corporate Flight Bookings.

The three mistakes that sink candidates

1. Building a size-n prefix array. Then every range sum needs a branch for i == 0, and the branch is where the bug lives. Use n + 1 with a leading zero and the arithmetic stays uniform.

2. Forgetting the {0: 1} seed. The counting template misses every subarray that starts at index 0. It is a one-line fix and a very common failure, so make the seed the first line you write.

3. Reaching for sliding window when negatives are allowed. The window approach looks correct, runs fast, and returns wrong answers on inputs the interviewer has ready. Read the constraints before choosing, and say which property you are relying on.

Practice ladder

In order, each rung adding one wrinkle.

1. Running Sum of 1d Array (E): the construction alone.
2. Range Sum Query Immutable (E): the identity behind an API.
3. Find Pivot Index (E): prefix against suffix.
4. Subarray Sum Equals K (M): the hash map template and the seed.
5. Contiguous Array (M): the 0-to--1 transformation.
6. Continuous Subarray Sum (M): storing remainders instead of totals.
7. Product of Array Except Self (M): prefix and suffix, no division.
8. Range Sum Query 2D Immutable (M): inclusion and exclusion in two dimensions.
9. Stretch: Corporate Flight Bookings (M), the difference array in reverse.

Then write the tell in your own words ("I should suspect prefix sums when ___") and move on. Recognition, not volume, is the skill.

The takeaway

One identity (a range sum is the difference of two prefixes), one construction detail that prevents most bugs (size n + 1 with a leading zero), one extension that handles the harder half of the family (a hash map of prefix counts, seeded with {0: 1}), and one boundary worth stating (negatives rule out sliding window and leave prefix sums standing). The full map of where this sits among the other 41 patterns is in the complete pattern guide. Next in the series: Backtracking, where one template covers subsets, permutations, and combinations.

Go deeper: Grokking the Coding Interview teaches all 42 patterns (32 common + 10 advanced) across 300+ sequenced problems, for a one-time $79 with lifetime access. Short on time? Grokking 75 includes the essential prefix sum problems in its 6-week plan.

FAQs

What is a prefix sum in simple terms? An array where each entry holds the total of everything before it. Build it once in O(n), and afterwards the sum of any range is one subtraction, because the sum of nums[i..j] equals prefix[j+1] - prefix[i].

Why should the prefix array have n + 1 entries? So that prefix[0] can represent the empty prefix, which is 0. That single extra slot means ranges starting at index 0 need no special handling, and it removes the most common source of off-by-one errors in this pattern.

When do I use prefix sums instead of a sliding window? When the input can contain negative numbers, or when the question asks you to count qualifying subarrays rather than find one shortest or longest window. Sliding window depends on the sum growing as the window grows, which negative values break. Prefix sums make no such assumption.

How does the hash map version of prefix sum work? A subarray sums to k exactly when two prefixes differ by k. So while scanning, you look up how many earlier prefixes equal running - k and add that count to the answer, then record the current prefix. Seed the map with {0: 1} so subarrays starting at index 0 are counted.

Is prefix sum asked at FAANG companies? Yes, most often in disguise. Subarray Sum Equals K and Contiguous Array are standard screens, Product of Array Except Self is an Amazon and Meta regular, and 2D range queries appear in follow-ups. The tell is usually the word "subarray" combined with a total.