Chapter 23 of 65

Prefix Sum

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  2

the running totals are:

3
3 + 1             = 4
3 + 1 + 4         = 8
3 + 1 + 4 + 1     = 9
... and so on

The 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  25

So 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) = 25

Why This Matters

Approach

Preprocessing

Each query

q queries in total

Loop over the range every time

None

O(n)

O(n × q)

Prefix sum

O(n)

O(1)

O(n + q)

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
-1

This 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) - k

So, 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
3

Time 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    6

We 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: 45

The 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] -= value

After 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

O(n)

O(n)

Range sum query

O(1)

-

Pivot index

O(n)

O(1)

Subarray sum equals k

O(n) average

O(n)

Product except self

O(n)

O(1) besides output

Build 2D prefix table

O(rows × cols)

O(rows × cols)

Rectangle sum query

O(1)

-

Difference array (u updates)

O(n + u)

O(n)


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, O(1) each

Extra space

Usually O(1)

Usually O(n)

Data changes often?

-

Needs rebuilding (O(n)) after each change

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

  1. Running Sum of 1d Array

  2. Range Sum Query - Immutable

  3. Find Pivot Index

  4. Subarray Sum Equals K

  5. Continuous Subarray Sum

  6. Subarray Sums Divisible by K

  7. Contiguous Array (equal number of 0s and 1s)

  8. Product of Array Except Self

  9. Range Sum Query 2D - Immutable

  10. 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 updates

Prefix sums trade a little preprocessing and memory for instant answers: compute the running totals once, and every range question becomes a simple subtraction.