Prefix Sum: 7 Practice Problems from Easy to Hard

Coding Patterns - Guide to 30 Core Algorithm Patterns

Prefix Sum: Complete Guide with Range Query Examples

Welcome to the prefix sum practice set. If the mechanics feel shaky, the code templates have the range-query class, the counting variant, and the difference array in all six languages. Each problem below has a hint, a visual walkthrough, and the complete solution.

Recommended Study Order

The problems climb in a deliberate order. Running Sum of 1d Array teaches the build pass with nothing else going on, so you see the running total in its purest form. Find Pivot Index adds the total-minus-left trick that powers most one-pass prefix solutions. Range Sum Query - Immutable is the class version you will write on a whiteboard, and Subarray Sum Equals K layers the hashmap on top, which is where most of the difficulty in this family lives. Range Sum Query 2D - Immutable extends the idea to grids, Corporate Flight Bookings shows the difference-array mirror, and Number of Submatrices That Sum to Target forces you to combine the 2D and hashmap techniques under one roof. Skip around only if you are already comfortable with the earlier ones; the later problems assume them.

The order above is designed to build intuition progressively. The app schedules your reviews so you do not forget the Easy patterns while grinding Hard ones. Set up your review schedule .

Easy Problems

1. Running Sum of 1d Array

LeetCode 1480 | Difficulty: Easy

Brief: return an array where each element is the sum of all the original elements up to that index.
Why this pattern: this problem is the definition of the prefix sum. The running total is exactly the prefix array, and nothing else is asked of you.
Hint: you can overwrite the input array. When you reach index i, the value you need is already sitting in nums[i - 1].

Visual:

    graph LR
    A["1, 2, 3, 4"] --> B["1, 3, 6, 10"]
    B --> C["nums[1] += nums[0]"]
    C --> D["nums[2] += nums[1]"]
    D --> E["nums[3] += nums[2]"]
    E --> F["Done"]

Code:

var runningSum = function(nums) {
    for (let i = 1; i < nums.length; i++) {
        nums[i] += nums[i - 1];
    }
    return nums;
};

The loop starts at index 1 because index 0 is its own running sum. Each step reads the accumulated total from the previous slot and adds the current element, so the array turns into its own prefix array in place. The complexity is

O(N)

time and

O(1)

extra space, which only works because the original values are never needed again.

2. Find Pivot Index

LeetCode 724 | Difficulty: Easy

Brief: find the index where the sum of the elements to the left equals the sum of the elements to the right.
Why this pattern: the left sum is a prefix sum by definition. With the total in hand, you never need to compute the right sum separately.
Hint: keep a running left sum. The right sum is always total - leftSum - nums[i].

Visual:

    graph TD
    A["nums = 1, 7, 3, 6, 5, 6, total = 28"] --> B["i = 0, left = 0, right = 27"]
    B --> C["i = 1, left = 1, right = 20"]
    C --> D["i = 2, left = 8, right = 17"]
    D --> E["i = 3, left = 11, right = 11"]
    E --> F["Return 3"]

Code:

var pivotIndex = function(nums) {
    const total = nums.reduce((a, b) => a + b, 0);
    let leftSum = 0;

    for (let i = 0; i < nums.length; i++) {
        if (leftSum === total - leftSum - nums[i]) {
            return i;
        }
        leftSum += nums[i];
    }
    return -1;
};

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        total = sum(nums)
        left_sum = 0

        for i, num in enumerate(nums):
            if left_sum == total - left_sum - num:
                return i
            left_sum += num

        return -1

The trick is the one-pass form of the prefix idea. Instead of building the whole prefix array, you carry the left sum forward and derive the right sum from the total. When the two match, that index is the answer. The check uses nums[i] explicitly so the pivot element itself is excluded from both sides. This runs in

O(N)

time and

O(1)

space.

Medium Problems

3. Range Sum Query - Immutable

LeetCode 303 | Difficulty: Medium

Brief: implement a class that answers many sumRange(left, right) queries on a fixed array.
Why this pattern: this is the textbook use case. One build, unlimited queries, each costing
O(1)
.
Hint: store the prefix array so sumRange(left, right) is exactly one subtraction with no loop.

Visual:

    graph TD
    A["nums = -2, 0, 3, -5, 2, -1"] --> B["prefix = 0, -2, -2, 1, -4, -2, -3"]
    B --> C["sumRange(0, 2) = prefix[3] - prefix[0]"]
    C --> D["= 1 - 0 = 1"]
    B --> E["sumRange(2, 5) = prefix[6] - prefix[2]"]
    E --> F["= -3 - (-2) = -1"]

Code:

var NumArray = function(nums) {
    this.prefix = new Array(nums.length + 1).fill(0);
    for (let i = 0; i < nums.length; i++) {
        this.prefix[i + 1] = this.prefix[i] + nums[i];
    }
};

NumArray.prototype.sumRange = function(left, right) {
    return this.prefix[right + 1] - this.prefix[left];
};

class NumArray
    def initialize(nums)
        @prefix = [0]
        nums.each do |num|
            @prefix << @prefix.last + num
        end
    end

    def sum_range(left, right)
        @prefix[right + 1] - @prefix[left]
    end
end

Notice the constructor is the entire algorithm. The prefix array is one element longer than the input, and prefix[i] stores the sum of the first i elements. The query then reads two slots and subtracts. There is nothing to loop over, which is why thousands of queries cost the same as one. Note the C++ and Go versions use 64-bit integers internally because cumulative sums can overflow a 32-bit int on large inputs.

4. Subarray Sum Equals K

LeetCode 560 | Difficulty: Medium

Brief: count the number of contiguous subarrays whose sum equals k.
Why this pattern: any subarray sum is a difference of two prefix sums. Counting how many pairs differ by k is a hashmap lookup per prefix, not a search.
Hint: seed the hashmap with {0: 1} before the loop. Subarrays that start at index 0 need that empty prefix to be found.

Visual:

    graph TD
    A["nums = 1, 2, 3, k = 3"] --> B["prefix 1, seen {0:1}"]
    B --> C["prefix 3, need 0, seen {0:1, 1:1}"]
    C --> D["found 1, count 1, seen {0:1, 1:1, 3:1}"]
    D --> E["prefix 6, need 3, seen {0:1, 1:1, 3:1}"]
    E --> F["found 1, count 2, answer 2"]

Code:

var subarraySum = function(nums, k) {
    const seen = new Map();
    seen.set(0, 1);
    let sum = 0;
    let count = 0;

    for (const num of nums) {
        sum += num;
        // An earlier prefix of (sum - k) means the subarray
        // between that prefix and here sums to exactly k.
        count += seen.get(sum - k) || 0;
        seen.set(sum, (seen.get(sum) || 0) + 1);
    }
    return count;
};

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        seen = {0: 1}
        total = 0
        count = 0

        for num in nums:
            total += num
            # If total - k has appeared before, every one of
            # those prefixes closes a subarray summing to k.
            count += seen.get(total - k, 0)
            seen[total] = seen.get(total, 0) + 1

        return count

class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> seen = new HashMap<>();
        seen.put(0, 1);
        int total = 0;
        int count = 0;

        for (int num : nums) {
            total += num;
            count += seen.getOrDefault(total - k, 0);
            seen.put(total, seen.getOrDefault(total, 0) + 1);
        }
        return count;
    }
}

The map stores how many times each prefix sum has appeared so far. When the running total reaches T, any earlier prefix equal to T - k marks the start of a valid subarray, so you add its count. The {0: 1} seed is the empty prefix; without it, the subarray starting at index 0 is invisible. This solves in

O(N)

time and

O(N)

space, which is optimal because you must look at every element.

5. Range Sum Query 2D - Immutable

LeetCode 304 | Difficulty: Medium

Brief: answer many submatrix sum queries on a fixed matrix.
Why this pattern: the 1D prefix array extends to two dimensions, and a submatrix sum becomes four corner reads instead of a double loop.
Hint: the build uses inclusion-exclusion too, subtracting the overlapping corner once.

Visual:

    graph TD
    A["prefix[2][3]"] --> B["whole area (0,0) to (1,2)"]
    B --> C["- prefix[0][3] strip above"]
    C --> D["- prefix[2][0] strip left"]
    D --> E["+ prefix[0][0] corner added back"]
    E --> F["= sum of (1,1) to (1,2)"]

Code:

var NumMatrix = function(matrix) {
    const h = matrix.length, w = matrix[0].length;
    this.prefix = Array.from({ length: h + 1 }, () => new Array(w + 1).fill(0));

    for (let i = 0; i < h; i++) {
        for (let j = 0; j < w; j++) {
            this.prefix[i + 1][j + 1] = matrix[i][j]
                + this.prefix[i][j + 1]
                + this.prefix[i + 1][j]
                - this.prefix[i][j];
        }
    }
};

NumMatrix.prototype.sumRegion = function(row1, col1, row2, col2) {
    return this.prefix[row2 + 1][col2 + 1]
        - this.prefix[row1][col2 + 1]
        - this.prefix[row2 + 1][col1]
        + this.prefix[row1][col1];
};

class NumMatrix:
    def __init__(self, matrix: List[List[int]]):
        h, w = len(matrix), len(matrix[0])
        self.prefix = [[0] * (w + 1) for _ in range(h + 1)]
        for i in range(h):
            for j in range(w):
                self.prefix[i + 1][j + 1] = (matrix[i][j]
                    + self.prefix[i][j + 1]
                    + self.prefix[i + 1][j]
                    - self.prefix[i][j])

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        return (self.prefix[row2 + 1][col2 + 1]
            - self.prefix[row1][col2 + 1]
            - self.prefix[row2 + 1][col1]
            + self.prefix[row1][col1])

class NumMatrix {
    private int[][] prefix;

    public NumMatrix(int[][] matrix) {
        int h = matrix.length, w = matrix[0].length;
        prefix = new int[h + 1][w + 1];
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                prefix[i + 1][j + 1] = matrix[i][j]
                    + prefix[i][j + 1]
                    + prefix[i + 1][j]
                    - prefix[i][j];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        return prefix[row2 + 1][col2 + 1]
            - prefix[row1][col2 + 1]
            - prefix[row2 + 1][col1]
            + prefix[row1][col1];
    }
}

class NumMatrix {
    vector<vector<long long>> prefix;
public:
    NumMatrix(vector<vector<int>>& matrix) {
        int h = matrix.size(), w = matrix[0].size();
        prefix.assign(h + 1, vector<long long>(w + 1, 0));
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                prefix[i + 1][j + 1] = matrix[i][j]
                    + prefix[i][j + 1]
                    + prefix[i + 1][j]
                    - prefix[i][j];
            }
        }
    }

    int sumRegion(int row1, int col1, int row2, int col2) {
        return (int)(prefix[row2 + 1][col2 + 1]
            - prefix[row1][col2 + 1]
            - prefix[row2 + 1][col1]
            + prefix[row1][col1]);
    }
};

type NumMatrix struct {
    prefix [][]int64
}

func Constructor(matrix [][]int) NumMatrix {
    h, w := len(matrix), len(matrix[0])
    prefix := make([][]int64, h+1)
    for i := range prefix {
        prefix[i] = make([]int64, w+1)
    }
    for i := 0; i < h; i++ {
        for j := 0; j < w; j++ {
            prefix[i+1][j+1] = int64(matrix[i][j])
                + prefix[i][j+1]
                + prefix[i+1][j]
                - prefix[i][j]
        }
    }
    return NumMatrix{prefix: prefix}
}

func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
    return int(this.prefix[row2+1][col2+1]
        - this.prefix[row1][col2+1]
        - this.prefix[row2+1][col1]
        + this.prefix[row1][col1])
}

class NumMatrix
    def initialize(matrix)
        h = matrix.length
        w = matrix[0].length
        @prefix = Array.new(h + 1) { Array.new(w + 1, 0) }
        (0...h).each do |i|
            (0...w).each do |j|
                @prefix[i + 1][j + 1] = matrix[i][j] +
                    @prefix[i][j + 1] + @prefix[i + 1][j] - @prefix[i][j]
            end
        end
    end

    def sum_region(row1, col1, row2, col2)
        @prefix[row2 + 1][col2 + 1] -
            @prefix[row1][col2 + 1] - @prefix[row2 + 1][col1] + @prefix[row1][col1]
    end
end

The build is the 2D version of the 1D loop. Each cell combines the rectangle above, the rectangle to the left, and the current matrix value, then subtracts the corner that was counted in both rectangles. The query reverses that process: it takes the big rectangle and peels away the top strip, the left strip, and then re-adds the corner that was removed twice. Build cost is

O(M*N)

and each query is

O(1)

6. Corporate Flight Bookings

LeetCode 1109 | Difficulty: Medium

Brief: apply many [first, last, seats] booking increments to a range of flights and return the final seat counts.
Why this pattern: this is the difference array, the update-side mirror of the prefix sum. One O(1) operation per booking replaces a loop over the whole range.
Hint: increment at the start, decrement just after the end, then one prefix pass over the result array. Watch the 1-indexed flight numbering.

Visual:

    graph TD
    A["bookings: [1,2,10], [2,3,20], [2,5,25], n = 5"] --> B["diff: +10 at 0, -10 at 2"]
    B --> C["+20 at 1, -20 at 3"]
    C --> D["+25 at 1, -25 at 5 (discarded)"]
    D --> E["diff = 10, 45, -10, -20, 0"]
    E --> F["prefix pass = 10, 55, 45, 25, 25"]

Code:

var corpFlightBookings = function(bookings, n) {
    const diff = new Array(n).fill(0);

    for (const [first, last, seats] of bookings) {
        diff[first - 1] += seats;
        if (last < n) {
            diff[last] -= seats;
        }
    }

    const result = new Array(n);
    let run = 0;
    for (let i = 0; i < n; i++) {
        run += diff[i];
        result[i] = run;
    }
    return result;
};

class Solution:
    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
        diff = [0] * n
        for first, last, seats in bookings:
            diff[first - 1] += seats
            if last < n:
                diff[last] -= seats

        result = []
        run = 0
        for i in range(n):
            run += diff[i]
            result.append(run)
        return result

class Solution {
    public int[] corpFlightBookings(int[][] bookings, int n) {
        int[] diff = new int[n];
        for (int[] booking : bookings) {
            int first = booking[0], last = booking[1], seats = booking[2];
            diff[first - 1] += seats;
            if (last < n) {
                diff[last] -= seats;
            }
        }

        int[] result = new int[n];
        int run = 0;
        for (int i = 0; i < n; i++) {
            run += diff[i];
            result[i] = run;
        }
        return result;
    }
}

class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        vector<int> diff(n, 0);
        for (auto& booking : bookings) {
            int first = booking[0], last = booking[1], seats = booking[2];
            diff[first - 1] += seats;
            if (last < n) {
                diff[last] -= seats;
            }
        }

        vector<int> result(n);
        int run = 0;
        for (int i = 0; i < n; i++) {
            run += diff[i];
            result[i] = run;
        }
        return result;
    }
};

func corpFlightBookings(bookings [][]int, n int) []int {
    diff := make([]int, n)
    for _, booking := range bookings {
        first, last, seats := booking[0], booking[1], booking[2]
        diff[first-1] += seats
        if last < n {
            diff[last] -= seats
        }
    }

    result := make([]int, n)
    run := 0
    for i := 0; i < n; i++ {
        run += diff[i]
        result[i] = run
    }
    return result
}

Flights are 1-indexed, so a booking starting at flight first lands at diff index first - 1. The +seats marks where the increment begins, and the -seats at last (the index after the last affected flight) marks where it ends. The final prefix pass over diff carries the running total forward, and every flight that was inside a booking range picks up the right count. This is

O(N + B)

time, where B is the number of bookings, and

O(N)

space.

Hard Problems

7. Number of Submatrices That Sum to Target

LeetCode 1074 | Difficulty: Hard

Brief: count how many submatrices in a matrix sum to a target value.
Why this pattern: compress each pair of rows into a 1D array of column sums, then apply the hashmap counting from Subarray Sum Equals K down the columns.
Hint: fix the top row, extend the bottom row downward, and maintain a running column-sum array. For each such pair, the problem reduces to a 1D counting problem.

Visual:

    graph TD
    A["Fix top row"] --> B["Extend bottom row"]
    B --> C["colSums = sum of rows top..bottom per column"]
    C --> D["Count subarrays of colSums equal to target"]
    D --> E["Repeat for every (top, bottom) pair"]

Code:

var numSubmatrixSumTarget = function(matrix, target) {
    const m = matrix.length, n = matrix[0].length;
    let count = 0;

    for (let top = 0; top < m; top++) {
        const colSums = new Array(n).fill(0);

        for (let bottom = top; bottom < m; bottom++) {
            for (let c = 0; c < n; c++) {
                colSums[c] += matrix[bottom][c];
            }

            // Count subarrays of colSums that sum to target.
            const seen = new Map();
            seen.set(0, 1);
            let run = 0;
            for (let c = 0; c < n; c++) {
                run += colSums[c];
                count += seen.get(run - target) || 0;
                seen.set(run, (seen.get(run) || 0) + 1);
            }
        }
    }
    return count;
};

class Solution:
    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:
        m, n = len(matrix), len(matrix[0])
        count = 0

        for top in range(m):
            # Column sums for the band between top and bottom.
            col_sums = [0] * n
            for bottom in range(top, m):
                for c in range(n):
                    col_sums[c] += matrix[bottom][c]

                # Every subarray of col_sums is one submatrix.
                seen = {0: 1}
                run = 0
                for c in range(n):
                    run += col_sums[c]
                    count += seen.get(run - target, 0)
                    seen[run] = seen.get(run, 0) + 1

        return count

class Solution {
    public int numSubmatrixSumTarget(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int count = 0;

        for (int top = 0; top < m; top++) {
            int[] colSums = new int[n];
            for (int bottom = top; bottom < m; bottom++) {
                for (int c = 0; c < n; c++) {
                    colSums[c] += matrix[bottom][c];
                }

                Map<Integer, Integer> seen = new HashMap<>();
                seen.put(0, 1);
                int run = 0;
                for (int c = 0; c < n; c++) {
                    run += colSums[c];
                    count += seen.getOrDefault(run - target, 0);
                    seen.put(run, seen.getOrDefault(run, 0) + 1);
                }
            }
        }
        return count;
    }
}

class Solution {
public:
    int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();
        int count = 0;

        for (int top = 0; top < m; top++) {
            vector<int> colSums(n, 0);
            for (int bottom = top; bottom < m; bottom++) {
                for (int c = 0; c < n; c++) {
                    colSums[c] += matrix[bottom][c];
                }

                unordered_map<int, int> seen;
                seen[0] = 1;
                int run = 0;
                for (int c = 0; c < n; c++) {
                    run += colSums[c];
                    count += seen[run - target];
                    seen[run]++;
                }
            }
        }
        return count;
    }
};

func numSubmatrixSumTarget(matrix [][]int, target int) int {
    m, n := len(matrix), len(matrix[0])
    count := 0

    for top := 0; top < m; top++ {
        colSums := make([]int, n)
        for bottom := top; bottom < m; bottom++ {
            for c := 0; c < n; c++ {
                colSums[c] += matrix[bottom][c]
            }

            seen := map[int]int{0: 1}
            run := 0
            for c := 0; c < n; c++ {
                run += colSums[c]
                count += seen[run-target]
                seen[run]++
            }
        }
    }
    return count
}

def num_submatrix_sum_target(matrix, target)
    m = matrix.length
    n = matrix[0].length
    count = 0

    (0...m).each do |top|
        col_sums = Array.new(n, 0)
        (top...m).each do |bottom|
            (0...n).each do |c|
                col_sums[c] += matrix[bottom][c]
            end

            seen = { 0 => 1 }
            run = 0
            (0...n).each do |c|
                run += col_sums[c]
                count += seen.fetch(run - target, 0)
                seen[run] = seen.fetch(run, 0) + 1
            end
        end
    end

    count
end

This problem is where the pattern earns its keep. Each submatrix is defined by a top row, a bottom row, and a contiguous range of columns. Fixing the top and bottom rows collapses the band into a 1D array of column sums, and then the exact hashmap trick from Subarray Sum Equals K counts every valid column range. Repeating for all

O(M^2)

row pairs gives

O(M^2 * N)

time overall, which beats the naive

O(M^2 * N^2)

check of every rectangle by a factor of N.

Hard problems are where patterns separate candidates who pass from candidates who get offers. Track your misses and review them on a spaced schedule so you do not repeat them in the real interview.

These seven problems cover the whole prefix sum family. Start with the build pass in Running Sum, learn to compute the right side from the total in Find Pivot Index, then layer on the class, the hashmap, the 2D grid, the difference array, and finally the combined challenge. By the end you should be able to look at a problem and tell within seconds whether it wants a prefix array, a hashmap of prefix sums, or a difference array. The code templates are worth revisiting once you have seen where each one actually shows up.

Done with these problems? The app has more, plus a review system that brings problems back right before you would forget them. Continue your prep .