Prefix Sums
A prefix sum array stores running totals so the sum of any range is one subtraction. Learn the template and how a hash map extends it to any subarray.
A prefix sum is a running total: the sum of everything from the start of an array up to a given point. Store those totals once, and the sum of any range becomes a single subtraction instead of a loop.
The idea
A bank statement shows a balance after each transaction. To find out how much you spent between the 5th and the 20th, you do not add up every transaction in between. You subtract the balance on the 5th from the balance on the 20th.
A prefix sum array is that column of balances:
numbers: 3 1 4 1 5
prefix: 0 3 4 8 9 14
↑
the total before any elementprefix[i] is the sum of the first i elements. The sum of the elements from index from to index to, both included, is:
prefix[to + 1] − prefix[from]Everything up to and including to, minus everything before from. For indexes 1 to 3 above: prefix[4] − prefix[1] = 9 − 3 = 6, which is 1 + 4 + 1.
When to use it
- The problem asks for the sum of a range, especially many ranges of the same array.
- It asks to find or count subarrays with a given sum, and the numbers can be negative, so a sliding window does not apply.
- It compares what is on the left of a position with what is on the right.
- More generally, whenever a brute-force solution keeps re-adding the same stretch of elements.
Form 1: build once, query many times
function prefixSums(numbers) {
const prefix = [0];
for (const value of numbers) {
prefix.push(prefix[prefix.length - 1] + value);
}
return prefix;
}
// Sum of numbers[from..to], both ends included.
function sumBetween(prefix, from, to) {
return prefix[to + 1] - prefix[from];
}Building takes O(n) once. After that every range sum is O(1), however long the range. Without the array, each query is a loop, and q queries cost O(n·q).
Why the array starts with 0
The prefix array has one more entry than the input, and the first is 0: the total before any element. That extra entry removes a special case. A range that starts at index 0 needs "everything before index 0", and prefix[0] supplies it. Leave it out and every formula needs an if for ranges that touch the start.
Form 2: running total with a hash map
Often the question is not "what is the sum of this range?" but "is there a range with this sum?". Rearranging the formula answers it in one pass.
A range ending at the current position sums to target exactly when:
(running total now) − (running total at some earlier point) = targetwhich is the same as saying that an earlier running total was equal to now − target. So keep every running total seen so far in a hash set, and at each step ask whether now − target is in it.
// Is there a run of consecutive elements that adds up to `target`?
function hasSubarrayWithSum(numbers, target) {
const seen = new Set([0]);
let running = 0;
for (const value of numbers) {
running += value;
if (seen.has(running - target)) return true;
seen.add(running);
}
return false;
}The set starts with 0 for the same reason the array does: it stands for the empty stretch before the first element, so a range starting at index 0 is found.
Swap the set for a map from each running total to how many times it has occurred and the same loop counts the ranges instead of detecting one. Store the earliest index of each total and it finds the longest such range.
This works with negative numbers, which is what sets it apart from the sliding window. The window relies on a sum only growing as the range grows; prefix sums rely on nothing but subtraction.
The same trick with other operations
Any operation that can be undone works the same way:
| Stored | Range result | Undo with |
|---|---|---|
| Running sum | Sum of a range | Subtraction |
| Running count of some value | How many in a range | Subtraction |
| Running XOR | XOR of a range | XOR again |
| Running product (no zeros) | Product of a range | Division |
Maximum and minimum cannot be undone, which is why a range maximum needs a different tool, such as the queue in Sliding Window Maximum.
Complexity
| Time | Space | |
|---|---|---|
| Build the prefix array | O(n) | O(n) |
| Each range sum afterwards | O(1) | |
| Running total with a set or map | O(n) | O(n) |
When only a left-versus-right comparison is needed, a single running total and the overall total are enough, and the extra space drops to O(1).
Common mistakes
- Off-by-one in the subtraction. With a leading 0, the range
fromtotoisprefix[to + 1] − prefix[from]. Usingprefix[to] − prefix[from]drops the last element. - Forgetting the starting 0 in the set or map. Ranges that begin at index 0 are then never found.
- Adding the current total to the map before looking up. When
targetis 0, the total would match itself and count an empty range. Look up first, then add. - Using a sliding window when numbers can be negative. Reach for prefix sums and a map instead.
- Rebuilding the prefix array for each query. The whole benefit is building it once.
Practice problems
| Problem | Difficulty | Time | Space | Read |
|---|---|---|---|---|
| Find Pivot Index | easy | O(n) | O(1) | Short read: 4 min |
| Subarray Sum Equals K | medium | O(n) | O(n) | Short read: 5 min |
| Shortest Subarray with Sum at Least K | hard | O(n) | O(n) | Medium read: 8 min |