Range Sum Query 2D - Immutable

NeetCode: Range Sum Query 2D - Immutable · LeetCode: 304. Range Sum Query 2D - Immutable · Difficulty: Medium

Implement NumMatrix with a constructor taking a 2D matrix and a method sumRegion(row1, col1, row2, col2) that returns the sum of the elements inside the rectangle with upper-left corner (row1, col1) and lower-right corner (row2, col2) (both inclusive). The matrix never changes, and there are many queries.

Example

Text

matrix = [[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]]
sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12

Brute force: add up the rectangle on every query

Keep a reference to the matrix (the constructor does not copy it) and loop over the requested cells on each query. Construction is free, but a query costs the area of the rectangle.

Java

class NumMatrix {
    private final int[][] matrix;

    public NumMatrix(int[][] matrix) {
        this.matrix = matrix;
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        int total = 0;
        for (int r = row1; r <= row2; r++) {
            for (int c = col1; c <= col2; c++) {
                total += matrix[r][c];
            }
        }
        return total;
    }
}

public class Main {
    public static void main(String[] args) {
        NumMatrix nm = new NumMatrix(new int[][]{
            {3, 0, 1, 4, 2},
            {5, 6, 3, 2, 1},
            {1, 2, 0, 1, 5},
            {4, 1, 0, 1, 7},
            {1, 0, 3, 0, 5}
        });
        System.out.println(nm.sumRegion(2, 1, 4, 3));
        System.out.println(nm.sumRegion(1, 1, 2, 2));
        System.out.println(nm.sumRegion(1, 2, 2, 4));
        System.out.println(nm.sumRegion(0, 0, 0, 0));
    }
}

Output

Time: O(1) to build, O(m · n) per query. Space: O(m · n) to hold the matrix.

Optimal: 2D prefix sums and inclusion-exclusion

Precompute pre[r][c], the sum of the rectangle from (0, 0) up to but not including row r and column c. The table has one extra row and column of zeros so that no index ever goes below 0. Build it with

pre[r+1][c+1] = matrix[r][c] + pre[r][c+1] + pre[r+1][c] - pre[r][c]

(the overlap pre[r][c] was added twice). A query is then the big rectangle minus the strip above, minus the strip on the left, plus the corner that was removed twice:

pre[row2+1][col2+1] - pre[row1][col2+1] - pre[row2+1][col1] + pre[row1][col1]

Java

class NumMatrix {
    private final int[][] pre;

    public NumMatrix(int[][] matrix) {
        int rows = matrix.length;
        int cols = rows == 0 ? 0 : matrix[0].length;
        pre = new int[rows + 1][cols + 1];
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                pre[r + 1][c + 1] = matrix[r][c] + pre[r][c + 1] + pre[r + 1][c] - pre[r][c];
            }
        }
    }

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

public class Main {
    public static void main(String[] args) {
        NumMatrix nm = new NumMatrix(new int[][]{
            {3, 0, 1, 4, 2},
            {5, 6, 3, 2, 1},
            {1, 2, 0, 1, 5},
            {4, 1, 0, 1, 7},
            {1, 0, 3, 0, 5}
        });
        System.out.println(nm.sumRegion(2, 1, 4, 3));
        System.out.println(nm.sumRegion(1, 1, 2, 2));
        System.out.println(nm.sumRegion(1, 2, 2, 4));
        System.out.println(nm.sumRegion(0, 0, 0, 0));
    }
}

Output

Time: O(m · n) to build, O(1) per query. Space: O((m + 1)(n + 1)) for the table.

The table is an int[][], matching LeetCode's signature. new int[rows + 1][cols + 1] is filled with zeros, which gives the border row and column. A prefix entry can exceed the int range for large inputs, because LeetCode allows values up to 10^5 in a 200 by 200 matrix. Java int arithmetic wraps, and the inclusion-exclusion formula adds and subtracts the same quantities, so a query whose true sum fits in int still comes out correct.