Ctrl K
Sign inStart free
Lesson

Prefix Sums

The idea in plain terms

Picture a bank statement that shows your balance after every transaction. How much did you spend between the 3rd and the 10th? You don't need to add up every receipt — just take the balance on the 10th, subtract the balance on the 2nd, and you have the answer in one step.

Prefix sums work the same way. Once, up front, we compute the "running balance" for every position in the array. After that, the sum of any range takes O(1) — a single subtraction.

What the prefix array looks like

Take this array:

30
11
42
13
54
95
26
the original array nums

Build prefix, where prefix[i] is the sum of the first i elements. It's one element longer and starts with zero:

00
31
42
83
94
145
236
257
prefix: prefix[0] = 0 — the sum of the empty start

The rule: prefix[i+1] = prefix[i] + nums[i]. Each number is the previous one plus the next element.

💡 The leading zero is the key trick. With it, the formula is the same for every range, and you don't need a special if for "the range starts at the very beginning".

A range sum in one subtraction

You need the sum of nums[2..4], that is 4 + 1 + 5 = 10:

30
11
l ↓ 42
13
r ↓ 54
95
26
the range nums[2..4]
00
31
l ↓ 42
83
94
r+1 ↓ 145
236
257
prefix[5] − prefix[2] = 14 − 4 = 10

The formula: sum(l..r) = prefix[r+1] - prefix[l]. prefix[r+1] holds everything up to and including r. Subtract everything before l, and exactly your range is left.

Code template

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

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

p = build_prefix([3, 1, 4, 1, 5, 9, 2])
print(range_sum(p, 2, 4))  # 10

Complexity

Operation Time Memory
Building prefix O(n) O(n)
One sum query O(1) —
q queries O(n + q) O(n)

Without prefixes every query would cost O(n), and all of them together O(n·q). That's a huge difference.

Prefixes + a hash map: counting subarrays

A common interview question: "how many subarrays have a sum of exactly k?" Trying every pair (l, r) is too slow, O(n²). Let's rewrite the condition with prefixes:

prefix[r+1] - prefix[l] = k ⟺ prefix[l] = prefix[r+1] - k

So for every right boundary you need to know how many times a prefix sum equal to current_prefix − k has appeared before. "How many times have I already seen this value?" is exactly what a hash map answers in O(1).

The line of reasoning:

  • walk the array left to right, keeping the current running sum;
  • in a hash map, store "prefix sum → how many times it has appeared";
  • on each step, look up the map first, then record the current prefix.

One pass: O(n) time and O(n) memory. Turning this into code is your exercise in this chapter's practice. Hint: think about what to put in the map before the first step so that subarrays starting at index 0 are counted. Remember our leading zero.

When prefixes beat a sliding window

A window relies on monotonicity: expand the window and the sum grows; shrink it and the sum drops. That only holds for non-negative numbers.

20
-11
22
13
-34
45
negative numbers break the window's logic

Here, adding -3 makes the sum drop. The window can't tell whether to move the left or the right boundary, and it may miss the answer. Prefixes don't care about signs: the formula prefix[r+1] - prefix[l] always holds.

Situation What to use
Only non-negative numbers, "shortest/longest range with sum ≥ k" Sliding window, O(1) memory
Negative numbers present Prefixes (+ hash map)
Many sum queries on an unchanging array Prefixes
Counting ranges with an exact sum Prefixes + hash map

How it sounds in an interview

"I'll compute a prefix sum array with a leading zero in O(n). Then the sum of range [l, r] is prefix[r+1] − prefix[l], computed in O(1). The array has negative numbers, so a window won't work: there's no monotonicity. I'll restate the condition on the range sum as a lookup for the right prefix in a hash map."

The interviewer wants to hear that you spotted the negative-number problem yourself.

Common mistakes

  • Off by one. Mixing up prefix[r] and prefix[r+1]. Check the formula on a single-element range: prefix[i+1] − prefix[i] should give nums[i].
  • Forgot the leading zero. Ranges starting at index 0 come out wrong.
  • Overflow. In Java, C++ and Go, a sum of many ints easily exceeds the type's limit, so store prefixes in long/long long/int64.
  • A window on negative numbers. The code looks right and passes simple tests, but fails on tricky ones.
  • Order of hash map operations. If you record the current prefix before checking, you can count an empty subarray or count the same one twice.

Now you have a tool that turns "sum of a range" into a single subtraction. Next, let's lock it in with some problems.