Imagine you are tracking your daily expenses for a month. Your friend keeps asking questions like:
"How much did you spend from day 5 to day 12?"
"What about day 1 to day 20?"
"And day 15 to day 30?"
You could add up the days again for every question. But a smarter way is to keep a running total: the total spent up to each day. Then any range is just one subtraction:
spent from day 5 to day 12 = (total up to day 12) - (total up to day 4)This running total is called a prefix sum. It is a small idea with a huge number of uses in DSA and coding interviews.
What is a Prefix Sum?
A prefix sum array stores, at each position, the sum of all elements from the start of the array up to that position. It lets us find the sum of any subarray in O(1) time after O(n) preprocessing.
For the array:
Index: 0 1 2 3 4 5 6
arr: 3 1 4 1 5 9 2the running totals are:
3
3 + 1 = 4
3 + 1 + 4 = 8
3 + 1 + 4 + 1 = 9
... and so onThe Extra Zero Trick
In practice, we usually make the prefix array one element longer and put a 0 at the start:
prefix[0] = 0 (sum of nothing)
prefix[i + 1] = prefix[i] + arr[i]Index: 0 1 2 3 4 5 6 7
prefix: 0 3 4 8 9 14 23 25So prefix[i] is the sum of the first i elements (arr[0] to arr[i - 1]).
The extra zero removes a special case, as you will see next.
Range Sum Query
Problem: Answer many queries of the form "what is the sum of arr[left..right]?"
The sum of the first right + 1 elements is prefix[right + 1]. The sum of the first left elements is prefix[left]. Subtract them and only the range remains:
sum(left, right) = prefix[right + 1] - prefix[left]For example, sum(2, 5):
arr: 3 1 [4 1 5 9] 2
↑ ↑
left=2 right=5
prefix[6] = 3 + 1 + 4 + 1 + 5 + 9 = 23
prefix[2] = 3 + 1 = 4
sum(2, 5) = 23 - 4 = 19 (4 + 1 + 5 + 9 = 19 ✓)Without the extra zero, a query starting at index 0 would need an if statement. With it, the same formula works for every range.
Range Sum in Java
import java.util.Arrays;
class Main {
static int[] buildPrefix(int[] arr) {
int[] prefix = new int[arr.length + 1];
for (int i = 0; i < arr.length; i++) {
prefix[i + 1] = prefix[i] + arr[i];
}
return prefix;
}
// Sum of arr[left..right], both inclusive
static int rangeSum(int[] prefix, int left, int right) {
return prefix[right + 1] - prefix[left];
}
public static void main(String[] args) {
int[] arr = {3, 1, 4, 1, 5, 9, 2};
int[] prefix = buildPrefix(arr);
System.out.println("Prefix: " + Arrays.toString(prefix));
System.out.println("Sum(0, 2) = " + rangeSum(prefix, 0, 2));
System.out.println("Sum(2, 5) = " + rangeSum(prefix, 2, 5));
System.out.println("Sum(4, 4) = " + rangeSum(prefix, 4, 4));
System.out.println("Sum(0, 6) = " + rangeSum(prefix, 0, 6));
}
}Output:
Prefix: [0, 3, 4, 8, 9, 14, 23, 25]
Sum(0, 2) = 8
Sum(2, 5) = 19
Sum(4, 4) = 5
Sum(0, 6) = 25Why This Matters
Approach | Preprocessing | Each query |
|
|---|---|---|---|
Loop over the range every time | None |
|
|
Prefix sum |
|
|
|
With n = 1,00,000 elements and q = 1,00,000 queries, the first approach can need around 1010 operations, while the prefix sum needs about 2 × 105.
The extra space is O(n) for the prefix array.
Example: Pivot (Equilibrium) Index
Problem: Find an index where the sum of the elements on its left equals the sum of the elements on its right. Return -1 if none exists.
nums = [1, 7, 3, 6, 5, 6]
Index 3: left = 1 + 7 + 3 = 11
right = 5 + 6 = 11 ✓We don't even need a full prefix array here. If we know the total sum and the running left sum, then:
rightSum = total - leftSum - nums[i]class Main {
static int pivotIndex(int[] nums) {
int total = 0;
for (int x : nums) {
total += x;
}
int leftSum = 0;
for (int i = 0; i < nums.length; i++) {
int rightSum = total - leftSum - nums[i];
if (leftSum == rightSum) {
return i;
}
leftSum += nums[i];
}
return -1;
}
public static void main(String[] args) {
System.out.println(pivotIndex(new int[] {1, 7, 3, 6, 5, 6}));
System.out.println(pivotIndex(new int[] {1, 2, 3}));
}
}Output:
3
-1This runs in O(n) time with O(1) extra space.
Example: Count Subarrays with Sum Equal to K
This is one of the most important prefix sum interview problems.
Problem: Given an array of integers (which may contain negative numbers) and a number k, count the number of contiguous subarrays whose sum is exactly k.
In the Sliding Window chapter you saw that a window cannot handle negative numbers reliably. Prefix sums can.
The Key Insight
In this section, prefix(i) means the sum of nums[0..i] (both inclusive), and prefix(-1) = 0 stands for the empty prefix. The sum of a subarray from index j to index i is:
sum(j..i) = prefix(i) - prefix(j - 1)We want this to equal k:
prefix(i) - prefix(j - 1) = k
⇒ prefix(j - 1) = prefix(i) - kSo, while scanning left to right with a running prefix sum, we ask at each index:
"How many earlier prefix sums were equal to
currentPrefix - k?"
Each one of them marks the start of a subarray that ends here and sums to k.
To count earlier prefix sums quickly, we store them in a HashMap (prefix sum → how many times we've seen it). HashMap is covered in detail in a later chapter. For now, all you need is: getOrDefault(key, 0) returns the stored count or 0, and put(key, value) stores a count. Both take O(1) time on average.
Trace
nums = [1, 1, 1], k = 2
seen = {0: 1} ← the empty prefix (sum 0) before index 0
i=0: prefix=1, need 1-2=-1 → seen 0 times count=0 seen={0:1, 1:1}
i=1: prefix=2, need 2-2=0 → seen 1 time count=1 seen={0:1, 1:1, 2:1}
i=2: prefix=3, need 3-2=1 → seen 1 time count=2 seen={0:1, 1:1, 2:1, 3:1}
Answer: 2 ([1, 1] at indexes 0-1 and [1, 1] at indexes 1-2)The starting entry {0: 1} is essential. It represents subarrays that start at index 0. Forgetting it is the most common bug in this problem.
import java.util.HashMap;
class Main {
static int subarraySum(int[] nums, int k) {
HashMap<Integer, Integer> seen = new HashMap<>();
seen.put(0, 1); // empty prefix: sum 0 has been seen once
int prefix = 0;
int count = 0;
for (int x : nums) {
prefix += x;
// How many earlier prefixes equal prefix - k?
count += seen.getOrDefault(prefix - k, 0);
seen.put(prefix, seen.getOrDefault(prefix, 0) + 1);
}
return count;
}
public static void main(String[] args) {
System.out.println(subarraySum(new int[] {1, 1, 1}, 2));
System.out.println(subarraySum(new int[] {3, 4, 7, 2, -3, 1, 4, 2}, 7));
System.out.println(subarraySum(new int[] {1, -1, 0}, 0));
}
}Output:
2
4
3Time complexity: O(n) on average. Space complexity: O(n) for the map. The brute-force solution that checks every subarray is O(n²).
Example: Product of Array Except Self
The prefix idea is not limited to sums. We can build "prefix products" too.
Problem: Return an array where answer[i] is the product of all elements except nums[i], without using division.
The product of everything except nums[i] is:
(product of everything to the left of i) × (product of everything to the right of i)nums: 1 2 3 4
left product: 1 1 2 6
right product: 24 12 4 1
answer: 24 12 8 6We can store the left products in the answer array, then sweep from the right with a single variable for the right product:
import java.util.Arrays;
class Main {
static int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] answer = new int[n];
// answer[i] = product of everything to the LEFT of i
answer[0] = 1;
for (int i = 1; i < n; i++) {
answer[i] = answer[i - 1] * nums[i - 1];
}
// Multiply by product of everything to the RIGHT of i
int suffix = 1;
for (int i = n - 1; i >= 0; i--) {
answer[i] *= suffix;
suffix *= nums[i];
}
return answer;
}
public static void main(String[] args) {
System.out.println(Arrays.toString(productExceptSelf(new int[] {1, 2, 3, 4})));
}
}Output:
[24, 12, 8, 6]This runs in O(n) time and uses O(1) extra space apart from the output array.
2D Prefix Sum
Prefix sums also work on grids, which you learned about in the 2D Arrays chapter.
Problem: Find the sum of any rectangle inside a matrix quickly.
Define p[r][c] as the sum of all cells above and to the left of (r, c), that is, the rectangle from (0, 0) to (r - 1, c - 1). Again we add an extra row and column of zeros.
To build it:
p[r+1][c+1] = grid[r][c] + p[r][c+1] + p[r+1][c] - p[r][c]We subtract p[r][c] because the top-left area was added twice (once in the block above and once in the block to the left).
To query the rectangle from (r1, c1) to (r2, c2):
sum = p[r2+1][c2+1] - p[r1][c2+1] - p[r2+1][c1] + p[r1][c1]We remove the strip above and the strip to the left, then add back the corner that was removed twice. This is the inclusion-exclusion idea.
class Main {
public static void main(String[] args) {
int[][] grid = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
int rows = grid.length;
int cols = grid[0].length;
int[][] p = new int[rows + 1][cols + 1];
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
p[r + 1][c + 1] = grid[r][c]
+ p[r][c + 1]
+ p[r + 1][c]
- p[r][c];
}
}
// Sum of the rectangle from (r1, c1) to (r2, c2), inclusive
int r1 = 1, c1 = 1, r2 = 2, c2 = 2;
int sum = p[r2 + 1][c2 + 1]
- p[r1][c2 + 1]
- p[r2 + 1][c1]
+ p[r1][c1];
System.out.println("Sum of bottom-right 2x2 block: " + sum);
System.out.println("Sum of whole grid: " + p[rows][cols]);
}
}Output:
Sum of bottom-right 2x2 block: 28
Sum of whole grid: 45The bottom-right 2×2 block is 5 + 6 + 8 + 9 = 28. Building the table takes O(rows × cols), and every rectangle query takes O(1).
Difference Array: The Reverse of Prefix Sum
Prefix sums make range queries fast. A difference array makes range updates fast.
Problem: Start with an array of zeros. Apply many updates of the form "add value to every index from l to r". Then print the final array.
Updating every index in the range each time costs O(n) per update. Instead, for each update we only mark where the change starts and where it stops:
diff[l] += value
diff[r + 1] -= valueAfter all updates, a prefix sum over diff spreads each change across its range.
n = 6, updates: (1, 3, +10), (2, 5, +5), (0, 1, +2)
diff after updates: [2, 10, 3, 0, -10, 0, -5]
prefix sum of diff: [2, 12, 15, 15, 5, 5]import java.util.Arrays;
class Main {
public static void main(String[] args) {
int n = 6;
int[] diff = new int[n + 1];
// Each update: add value to every index from l to r (inclusive)
int[][] updates = {
{1, 3, 10},
{2, 5, 5},
{0, 1, 2}
};
for (int[] u : updates) {
int l = u[0], r = u[1], value = u[2];
diff[l] += value;
diff[r + 1] -= value;
}
int[] result = new int[n];
int running = 0;
for (int i = 0; i < n; i++) {
running += diff[i];
result[i] = running;
}
System.out.println(Arrays.toString(result));
}
}Output:
[2, 12, 15, 15, 5, 5]Each update takes O(1), and the final prefix pass takes O(n). So u updates cost O(n + u) instead of O(n × u).
Time and Space Complexity
Task | Time | Extra Space |
|---|---|---|
Build 1D prefix array |
|
|
Range sum query |
| - |
Pivot index |
|
|
Subarray sum equals k |
|
|
Product except self |
|
|
Build 2D prefix table |
|
|
Rectangle sum query |
| - |
Difference array (u updates) |
|
|
Prefix Sum vs Sliding Window
Sliding Window | Prefix Sum | |
|---|---|---|
Works with negative numbers? | Not for sum-based variable windows | Yes |
Many range queries? | No | Yes, |
Extra space | Usually | Usually |
Data changes often? | - | Needs rebuilding ( |
If the array is updated frequently and you need range sums, more advanced structures such as a Fenwick Tree (Binary Indexed Tree) or a Segment Tree are used. They are beyond the scope of this chapter.
Common Mistakes
1. Off-by-One Errors
Decide on one convention and stick to it. With the extra-zero convention: prefix has length n + 1, and sum(l, r) = prefix[r + 1] - prefix[l].
2. Integer Overflow
A prefix sum can grow much larger than any single element. If the array has 105 elements of size up to 109, the total can reach 1014, which does not fit in an int (maximum about 2.1 × 109). Use a long[] prefix array in such cases.
3. Forgetting seen.put(0, 1)
In "subarray sum equals k", without this entry you miss every subarray that starts at index 0.
4. Updating the Map Too Early
In the same problem, look up prefix - k before adding the current prefix to the map. Otherwise, when k = 0, the current prefix would match itself and count an empty subarray.
5. Using a Window When Negatives Are Present
If the array can contain negative numbers and you need subarrays with a given sum, reach for prefix sums, not a sliding window.
Practice Problems
Running Sum of 1d Array
Range Sum Query - Immutable
Find Pivot Index
Subarray Sum Equals K
Continuous Subarray Sum
Subarray Sums Divisible by K
Contiguous Array (equal number of 0s and 1s)
Product of Array Except Self
Range Sum Query 2D - Immutable
Corporate Flight Bookings (difference array)
The Main Idea
A prefix sum stores running totals so that any range sum becomes a single subtraction:
prefix[0] = 0
prefix[i + 1] = prefix[i] + arr[i]
sum(l, r) = prefix[r + 1] - prefix[l]Remember its main uses:
Range sum queries → O(1) per query
Subarray sum equals k → prefix sum + HashMap
Prefix / suffix products → product except self
2D prefix sum → rectangle sums
Difference array → O(1) range updatesPrefix sums trade a little preprocessing and memory for instant answers: compute the running totals once, and every range question becomes a simple subtraction.