Prefix Sum

1The mental model (what this really is)#

Prefix sum is a precomputation trick. Compute running totals once, up front, then stop recomputing ranges.

• The idea: instead of re-adding a range every time you need it, compute running totals once in a single O(n) pass.
• The payoff: any range sum becomes a single subtraction, O(1), no matter how long the range is.
• The picture: walk along a row of numbers keeping a running tally of everything seen so far. At each position, write down the total. That list of running totals is your prefix sum array.

Why the subtraction works.

• Know the total up to index j and the total up to index i-1, and the sum strictly between them is just the difference.
• You have turned "add up k elements" into "subtract two numbers."
• A range of length 1 and a range of length 10,000 now cost exactly the same. That is the whole idea.

The deeper version that wins harder problems.

• A running total tells you where you have been.
• Remember every total you have seen (usually in a hash map keyed by prefix value) and you can answer "has the total ever been this exact value before, and how many times?"
• That single idea unlocks subarray-counting problems that look nothing like simple range sums at first glance.
• It is the version that separates a passing Meta phone screen from a failing one.

2How to recognize it (the signals in a problem)#

Train your eye for these. When two or three show up together, reach for prefix sum before you write a single loop.

• Sums (or counts, or products) over ranges or subarrays. "Sum between index i and j." "Number of subarrays where..."
• Many queries on a static array. Lots of range sums, array does not change. Precompute once in O(n), then answer each of q queries in O(1) instead of O(n).
• A nested loop whose inner loop re-adds elements you already added on the previous outer step. That re-adding is the smell. If your inner loop recomputes a sum from scratch, you are paying O(n²) for something that is O(n).
• "Contiguous subarray" plus a target sum or a count. This is the hash-map variant, the single most tested flavor in interviews.
• Words like "running total," "cumulative," or "so far." If you catch yourself saying them, that is the signal.
• 2D grids asking for sums of rectangles or submatrices. That is prefix sum in two dimensions.

3The template (how it works, with pseudocode)#

Start with the clean range-sum version. I strongly prefer a prefix array of length n+1 with a leading zero.

• It kills off-by-one bugs: every valid range maps to a clean subtraction with no special case at index 0.
• Candidates who index into a length-n array here lose two or three minutes fighting a boundary bug that a length-n+1 array just makes impossible.

# Build: prefix[k] = sum of the first k elements (so prefix[0] = 0)
prefix = [0] * (n + 1)
for i in range(n):
    prefix[i + 1] = prefix[i] + arr[i]

# Query: sum of arr[left .. right] inclusive
def range_sum(left, right):
    return prefix[right + 1] - prefix[left]

Why the +1 offset is the single best habit here.

• prefix[left] is "everything before left."
• prefix[right+1] is "everything through right."
• The difference is exactly the slice you want. No if left == 0 branch, ever.

Now the hash-map variant, for counting subarrays with a given sum k. This is the version that trips people up, so read it twice.

count = 0
running = 0
seen = { 0: 1 }   # one empty prefix, sum 0, seen once

for x in arr:
    running += x
    # if some earlier prefix equals (running - k),
    # then the subarray between then and now sums to k
    count += seen.get(running - k, 0)
    seen[running] = seen.get(running, 0) + 1

return count

The pivot that makes this work.

• A subarray ending at the current position sums to k exactly when running - k was a prefix total we have already seen.
• Every earlier time we saw that value is one more valid subarray, so we add the stored count, not 1.
• That is why seen stores occurrences, not just presence.
• Miss this and you undercount on any input with repeated prefix values.

Prefix sum turns "re-add k elements" into "subtract two numbers." Learn the subtraction and the rest is bookkeeping.

4A worked example (walk through one problem step by step)#

Problem: count the number of contiguous subarrays that sum to k. Let arr = [1, 2, 3, -2, 2] and k = 3.

• Brute force checks every start/end pair: O(n²), which on 20,000 elements is 400 million operations and a near-certain TLE.
• We will do it in one pass, O(n).

Set up: running = 0, count = 0, seen = {0: 1}.

• The {0: 1} matters. It represents the empty prefix before we start.
• It is what lets a subarray that begins at index 0 get counted. Drop it and every answer that starts at the front of the array silently disappears.

Walk through it:

x = 1. running = 1. We want earlier prefixes equal to running - k = 1 - 3 = -2. Is -2 in seen? No. count stays 0. Record running: seen = {0:1, 1:1}.

x = 2. running = 3. Look for 3 - 3 = 0. Is 0 in seen? Yes, once. So count = 1. That is the subarray [1, 2], which sums to 3. Correct. Record: seen = {0:1, 1:1, 3:1}.

x = 3. running = 6. Look for 6 - 3 = 3. Is 3 in seen? Yes, once. count = 2. The subarray between that earlier prefix and now is [3]. Sums to 3. Correct. Record: seen = {0:1, 1:1, 3:1, 6:1}.

x = -2. running = 4. Look for 4 - 3 = 1. Is 1 in seen? Yes, once. count = 3. The subarray is [2, 3, -2]. Check: 2 + 3 - 2 = 3. Correct, and notice it crossed a negative number. Prefix sum handles negatives for free, which is exactly why a sliding window fails here and this does not. Record: seen = {0:1, 1:1, 3:1, 6:1, 4:1}.

x = 2. running = 6. Look for 6 - 3 = 3. Is 3 in seen? Yes, once. count = 4. The subarray is [-2, 2]... wait, let me check: that earlier prefix of 3 was after index 2, so the subarray is from index 3 to 4, which is [-2, 2]. Sums to 0, not 3. Let me recheck. Prefix 3 occurred at 2 entries in, meaning after processing [1,2]. The current prefix is 6 after [1,2,3,-2,2]. The subarray between them is indices 2..4: [3, -2, 2]. Sums to 3. Correct. Record and finish.

Final count = 4. Four subarrays sum to 3: [1,2], [3], [2,3,-2], and [3,-2,2]. One pass, O(n).

5Variations and gotchas#

Each of these is the same subtraction idea wearing a different hat. Know them and you stop getting surprised.

• 2D prefix sum. For rectangle sums in a grid, build a 2D cumulative table where P[i][j] is the sum of the whole rectangle from the top-left corner to (i,j). A sub-rectangle uses inclusion-exclusion: take the big rectangle, subtract the strip above, subtract the strip to the left, then add back the top-left corner you subtracted twice. Four array lookups per query, O(1), after an O(m·n) build. The formula is P[r2][c2] - P[r1-1][c2] - P[r2][c1-1] + P[r1-1][c1-1], and padding the table with an extra zero row and column (same n+1 trick in both dimensions) removes the boundary checks.
• Prefix count / prefix of a condition. You do not have to sum raw values. Map each element to 0 or 1 based on a condition, then prefix-sum that. Now "how many elements satisfying X in this range" is O(1). Very common dressed-up version, and often the interviewer will not tell you it is prefix sum at all.
• Prefix XOR and prefix product. The subtraction trick generalizes to any invertible operation. XOR is its own inverse, so range XOR is prefix[right+1] XOR prefix[left]. Product works too if you handle zeros carefully, since you cannot divide to "subtract" a zero back out.
• Remainder / modular prefix sums. For "count subarrays whose sum is divisible by k," store running % k in the hash map instead of the raw running total. Two prefixes with the same remainder bound a subarray divisible by k. Mind negative remainders in languages where % can go negative (more on that below).
• Difference array (the inverse). When you need to apply many range updates and only read the result at the end, use a difference array: mark +val at the start index and -val just past the end index, then prefix-sum once to materialize the final array. It is prefix sum run backward, and it is the right answer to "add X to every element in range [l, r], repeated u times." That turns O(n·u) into O(n + u).

6Complexity#

The numbers are the whole argument for the pattern. Keep them at your fingertips.

Plain range-sum prefix:

• Build: O(n) time, O(n) extra space.
• Each query: O(1).

The rest of the family:

• Hash-map subarray counting: O(n) time, O(n) space for the map.
• 2D prefix: O(m·n) to build, O(1) per rectangle query.
• Difference array: O(n + u) for u updates, versus O(n·u) if you naively update each range.

On space.

• If you can afford to overwrite the input, some 1D cases run in O(1) extra space by storing the running sum in place.
• Mention it if the interviewer cares about space, but do not volunteer a destructive change to the caller's array without asking first.
• Quietly mutating an input is the kind of thing that costs you a point in a design-sensitive loop.

7Mistakes that cost people the round#

These are the exact ways I watch candidates lose a solvable problem. Every one is avoidable.

• Off-by-one on range boundaries. Mixing up inclusive and exclusive ends. The n+1 array with a leading zero makes this nearly impossible to get wrong. Use it.
• Forgetting the {0: 1} seed in the hash-map variant. Without it you miss every subarray that starts at index 0. The code runs, passes a couple small tests, fails the rest. Brutal to debug under pressure because nothing looks wrong.
• Storing presence instead of count. In the counting variant, using a set instead of a frequency map undercounts when the same prefix total appears more than once. You get a smaller number and do not know why.
• Updating the map before counting. Order matters. For "subarrays summing to k" you must count first, then record the current prefix, or you match a prefix against itself and count a bogus zero-length subarray.
• Reaching for prefix sum when the array mutates between queries. If updates are frequent, a prefix rebuild is O(n) per update and you have built the wrong thing. That is a Fenwick tree or segment tree signal.
• Negative modulo bugs. (-3) % 5 is not 2 in several languages (C++, Java, and JavaScript give -3). Normalize with ((x % k) + k) % k before you use a remainder as a hash key.
• Integer overflow. With large arrays of large values, the running total can blow past a 32-bit int. Use a 64-bit type in Java and C++. Python saves you here, but say it out loud so the interviewer knows you thought about it.
• Over-engineering. If there is exactly one query, you do not need a prefix array. A single accumulating loop is cleaner. Match the tool to the question.

8Your practice path#

Do them in this order. Each one adds exactly one new idea on top of the last.

Easy (get the core reflex):

• Running Sum of 1d Array
• Find Pivot Index
• Range Sum Query - Immutable

Medium (the real interview zone):

• Subarray Sum Equals K
• Contiguous Array
• Product of Array Except Self (the prefix/suffix cousin, great for seeing the idea run in both directions)
• Continuous Subarray Sum
• Range Sum Query 2D - Immutable
• Maximum Size Subarray Sum Equals k
• Subarray Sums Divisible by K

Harder (combine with other patterns):

• Count Number of Nice Subarrays
• Maximum Sum of Two Non-Overlapping Subarrays
• Number of Submatrices That Sum to Target

If you do nothing else:

• Internalize Subarray Sum Equals K until you can write it from memory in under five minutes, with the {0:1} seed and the count-before-record order both correct on the first try.
• That single problem is the skeleton for Contiguous Array, Subarray Sums Divisible by K, Count Number of Nice Subarrays, and most of the rest of the medium list.
• Learn one shape, pass five questions.

9Where this shows up#

Prefix sum is table stakes at the big product companies. It is rarely the whole problem and almost always the piece that makes a slow solution fast.

• Amazon and Google use it as a warm-up or as the hidden optimization inside a bigger question.
• Meta loves the subarray-counting flavor in phone screens. Subarray Sum Equals K and its relatives come up over and over.
• Fintech and trading shops lean on it constantly, where running totals over time series are the daily bread and a candidate who reaches for cumulative sums instantly looks like they have done the work before.
• More often than not it is buried. It is the piece that turns a slow solution into a fast one, hidden inside something that looks like a dynamic programming or a two-pointer question.
• Spot it fast and you buy yourself the ten minutes you will need for the hard part of the round.

Want to see which companies and rounds lean on this pattern most? Check the company guides to map it to where you are actually interviewing.