304. Range Sum Query 2D Immutable - Explanation

Description

You are given a 2D matrix matrix, handle multiple queries of the following type:

Calculate the sum of the elements of matrix inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

Implement the NumMatrix class:

NumMatrix(int[][] matrix) Initializes the object with the integer matrix matrix.
int sumRegion(int row1, int col1, int row2, int col2) Returns the sum of the elements of matrix inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).
You must design an algorithm where sumRegion works on O(1) time complexity.

Example 1:

Input: ["NumMatrix", "sumRegion", "sumRegion", "sumRegion"]
[[[[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]]], [2, 1, 4, 3], [1, 1, 2, 2], [1, 2, 2, 4]]

Output: [null, 8, 11, 12]

Explanation:
NumMatrix numMatrix = new NumMatrix([[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]]);
numMatrix.sumRegion(2, 1, 4, 3); // return 8 (i.e sum of the red rectangle)
numMatrix.sumRegion(1, 1, 2, 2); // return 11 (i.e sum of the green rectangle)
numMatrix.sumRegion(1, 2, 2, 4); // return 12 (i.e sum of the blue rectangle)

Constraints:

m == matrix.length
n == matrix[i].length
1 <= m, n <= 200
-10,000 <= matrix[i][j] <= 10,000
0 <= row1 <= row2 < m
0 <= col1 <= col2 < n
At most 10,000 calls will be made to sumRegion.

Topics

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

2D Arrays (Matrices) - Working with row and column indices to access and iterate over rectangular regions
Prefix Sums - Precomputing cumulative sums for constant-time range queries
Inclusion-Exclusion Principle - Computing 2D region sums by combining overlapping rectangular areas

1. Brute Force

Intuition

The most straightforward approach is to iterate through every cell in the specified rectangular region and sum up all the values. For each query, we simply loop from the top-left corner to the bottom-right corner and accumulate the result. While this is easy to implement, it becomes slow when we have many queries or large regions to sum.

Algorithm

Store the original matrix.
For each sumRegion(row1, col1, row2, col2) query:
- Initialize res = 0.
- Iterate through all rows from row1 to row2.
- For each row, iterate through all columns from col1 to col2.
- Add each cell value to res.
Return res.

class NumMatrix:

    def __init__(self, matrix: list[list[int]]):
        self.matrix = matrix

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        res = 0
        for r in range(row1, row2 + 1):
            for c in range(col1, col2 + 1):
                res += self.matrix[r][c]
        return res

public class NumMatrix {

    private int[][] matrix;

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

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

class NumMatrix {
private:
    vector<vector<int>> matrix;

public:
    NumMatrix(vector<vector<int>>& matrix) {
        this->matrix = matrix;
    }

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

class NumMatrix {
    /**
     * @param {number[][]} matrix
     */
    constructor(matrix) {
        this.matrix = matrix;
    }

    /**
     * @param {number} row1
     * @param {number} col1
     * @param {number} row2
     * @param {number} col2
     * @return {number}
     */
    sumRegion(row1, col1, row2, col2) {
        let res = 0;
        for (let r = row1; r <= row2; r++) {
            for (let c = col1; c <= col2; c++) {
                res += this.matrix[r][c];
            }
        }
        return res;
    }
}

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

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

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

type NumMatrix struct {
    matrix [][]int
}

func Constructor(matrix [][]int) NumMatrix {
    return NumMatrix{matrix: matrix}
}

func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
    res := 0
    for r := row1; r <= row2; r++ {
        for c := col1; c <= col2; c++ {
            res += this.matrix[r][c]
        }
    }
    return res
}

class NumMatrix(private val matrix: Array<IntArray>) {

    fun sumRegion(row1: Int, col1: Int, row2: Int, col2: Int): Int {
        var res = 0
        for (r in row1..row2) {
            for (c in col1..col2) {
                res += matrix[r][c]
            }
        }
        return res
    }
}

class NumMatrix {
    private var matrix: [[Int]]

    init(_ matrix: [[Int]]) {
        self.matrix = matrix
    }

    func sumRegion(_ row1: Int, _ col1: Int, _ row2: Int, _ col2: Int) -> Int {
        var res = 0
        for r in row1...row2 {
            for c in col1...col2 {
                res += matrix[r][c]
            }
        }
        return res
    }
}

Time & Space Complexity

Time complexity: $O(m * n)$ for each query.
Space complexity: $O(1)$

Where $m$ is the number of rows and $n$ is the number of columns in the matrix.

2. One Dimensional Prefix Sum

Intuition

Instead of summing every cell for each query, we can precompute prefix sums for each row. Each prefixSum[row][col] stores the sum of all elements from matrix[row][0] to matrix[row][col]. This way, finding the sum of any range within a single row takes constant time. For a rectangular region spanning multiple rows, we sum each row's contribution using its prefix sum.

Algorithm

Build a 2D prefix sum array where prefixSum[row][col] holds the cumulative sum of row row from column 0 to col.
For each sumRegion(row1, col1, row2, col2) query:
- Initialize res = 0.
- For each row from row1 to row2:
  - Add prefixSum[row][col2] to res.
  - If col1 > 0, subtract prefixSum[row][col1 - 1] from res.
Return res.

class NumMatrix:

    def __init__(self, matrix: list[list[int]]):
        self.prefixSum = [[0] * len(matrix[0]) for _ in range(len(matrix))]

        for row in range(len(matrix)):
            self.prefixSum[row][0] = matrix[row][0]
            for col in range(1, len(matrix[0])):
                self.prefixSum[row][col] = self.prefixSum[row][col - 1] + matrix[row][col]

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        res = 0
        for row in range(row1, row2 + 1):
            if col1 > 0:
                res += self.prefixSum[row][col2] - self.prefixSum[row][col1 - 1]
            else:
                res += self.prefixSum[row][col2]
        return res

public class NumMatrix {

    private int[][] prefixSum;

    public NumMatrix(int[][] matrix) {
        int rows = matrix.length, cols = matrix[0].length;
        prefixSum = new int[rows][cols];

        for (int row = 0; row < rows; row++) {
            prefixSum[row][0] = matrix[row][0];
            for (int col = 1; col < cols; col++) {
                prefixSum[row][col] = prefixSum[row][col - 1] + matrix[row][col];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        int res = 0;
        for (int row = row1; row <= row2; row++) {
            if (col1 > 0) {
                res += prefixSum[row][col2] - prefixSum[row][col1 - 1];
            } else {
                res += prefixSum[row][col2];
            }
        }
        return res;
    }
}

class NumMatrix {
private:
    vector<vector<int>> prefixSum;

public:
    NumMatrix(vector<vector<int>>& matrix) {
        int rows = matrix.size(), cols = matrix[0].size();
        prefixSum = vector<vector<int>>(rows, vector<int>(cols, 0));

        for (int row = 0; row < rows; row++) {
            prefixSum[row][0] = matrix[row][0];
            for (int col = 1; col < cols; col++) {
                prefixSum[row][col] = prefixSum[row][col - 1] + matrix[row][col];
            }
        }
    }

    int sumRegion(int row1, int col1, int row2, int col2) {
        int res = 0;
        for (int row = row1; row <= row2; row++) {
            if (col1 > 0) {
                res += prefixSum[row][col2] - prefixSum[row][col1 - 1];
            } else {
                res += prefixSum[row][col2];
            }
        }
        return res;
    }
};

class NumMatrix {
    /**
     * @param {number[][]} matrix
     */
    constructor(matrix) {
        this.prefixSum = Array.from({ length: matrix.length }, () =>
            Array(matrix[0].length).fill(0),
        );

        for (let row = 0; row < matrix.length; row++) {
            this.prefixSum[row][0] = matrix[row][0];
            for (let col = 1; col < matrix[0].length; col++) {
                this.prefixSum[row][col] =
                    this.prefixSum[row][col - 1] + matrix[row][col];
            }
        }
    }

    /**
     * @param {number} row1
     * @param {number} col1
     * @param {number} row2
     * @param {number} col2
     * @return {number}
     */
    sumRegion(row1, col1, row2, col2) {
        let res = 0;
        for (let row = row1; row <= row2; row++) {
            if (col1 > 0) {
                res +=
                    this.prefixSum[row][col2] - this.prefixSum[row][col1 - 1];
            } else {
                res += this.prefixSum[row][col2];
            }
        }
        return res;
    }
}

public class NumMatrix {
    private int[][] prefixSum;

    public NumMatrix(int[][] matrix) {
        int rows = matrix.Length;
        int cols = matrix[0].Length;
        prefixSum = new int[rows][];

        for (int i = 0; i < rows; i++) {
            prefixSum[i] = new int[cols];
            prefixSum[i][0] = matrix[i][0];
            for (int j = 1; j < cols; j++) {
                prefixSum[i][j] = prefixSum[i][j - 1] + matrix[i][j];
            }
        }
    }

    public int SumRegion(int row1, int col1, int row2, int col2) {
        int res = 0;
        for (int row = row1; row <= row2; row++) {
            if (col1 > 0) {
                res += prefixSum[row][col2] - prefixSum[row][col1 - 1];
            } else {
                res += prefixSum[row][col2];
            }
        }
        return res;
    }
}

type NumMatrix struct {
    prefixSum [][]int
}

func Constructor(matrix [][]int) NumMatrix {
    rows, cols := len(matrix), len(matrix[0])
    prefixSum := make([][]int, rows)

    for row := 0; row < rows; row++ {
        prefixSum[row] = make([]int, cols)
        prefixSum[row][0] = matrix[row][0]
        for col := 1; col < cols; col++ {
            prefixSum[row][col] = prefixSum[row][col-1] + matrix[row][col]
        }
    }

    return NumMatrix{prefixSum: prefixSum}
}

func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
    res := 0
    for row := row1; row <= row2; row++ {
        if col1 > 0 {
            res += this.prefixSum[row][col2] - this.prefixSum[row][col1-1]
        } else {
            res += this.prefixSum[row][col2]
        }
    }
    return res
}

class NumMatrix(matrix: Array<IntArray>) {
    private val prefixSum: Array<IntArray>

    init {
        val rows = matrix.size
        val cols = matrix[0].size
        prefixSum = Array(rows) { IntArray(cols) }

        for (row in 0 until rows) {
            prefixSum[row][0] = matrix[row][0]
            for (col in 1 until cols) {
                prefixSum[row][col] = prefixSum[row][col - 1] + matrix[row][col]
            }
        }
    }

    fun sumRegion(row1: Int, col1: Int, row2: Int, col2: Int): Int {
        var res = 0
        for (row in row1..row2) {
            res += if (col1 > 0) {
                prefixSum[row][col2] - prefixSum[row][col1 - 1]
            } else {
                prefixSum[row][col2]
            }
        }
        return res
    }
}

class NumMatrix {
    private var prefixSum: [[Int]]

    init(_ matrix: [[Int]]) {
        let rows = matrix.count
        let cols = matrix[0].count
        prefixSum = Array(repeating: Array(repeating: 0, count: cols), count: rows)

        for row in 0..<rows {
            prefixSum[row][0] = matrix[row][0]
            for col in 1..<cols {
                prefixSum[row][col] = prefixSum[row][col - 1] + matrix[row][col]
            }
        }
    }

    func sumRegion(_ row1: Int, _ col1: Int, _ row2: Int, _ col2: Int) -> Int {
        var res = 0
        for row in row1...row2 {
            if col1 > 0 {
                res += prefixSum[row][col2] - prefixSum[row][col1 - 1]
            } else {
                res += prefixSum[row][col2]
            }
        }
        return res
    }
}

Time & Space Complexity

Time complexity: $O(m)$
Space complexity: $O(m * n)$

Where $m$ is the number of rows and $n$ is the number of columns in the matrix.

3. Two Dimensional Prefix Sum

Intuition

We can extend prefix sums to two dimensions. The idea is to precompute sumMat[r][c] as the sum of all elements in the rectangle from (0, 0) to (r - 1, c - 1). To find the sum of any rectangular region, we use the inclusion-exclusion principle: take the sum up to the bottom-right corner, subtract the regions above and to the left, then add back the top-left corner (which was subtracted twice).

Algorithm

Create a prefix sum matrix sumMat of size (ROWS + 1) x (COLS + 1) initialized to zero.
Build the prefix sum matrix:
- For each row r, maintain a running prefix sum across columns.
- Set sumMat[r + 1][c + 1] = prefix + sumMat[r][c + 1].
For each sumRegion(row1, col1, row2, col2) query:
- Compute bottomRight = sumMat[row2 + 1][col2 + 1].
- Subtract above = sumMat[row1][col2 + 1].
- Subtract left = sumMat[row2 + 1][col1].
- Add back topLeft = sumMat[row1][col1].
Return bottomRight - above - left + topLeft.

class NumMatrix:

    def __init__(self, matrix: list[list[int]]):
        ROWS, COLS = len(matrix), len(matrix[0])
        self.sumMat = [[0] * (COLS + 1) for _ in range(ROWS + 1)]

        for r in range(ROWS):
            prefix = 0
            for c in range(COLS):
                prefix += matrix[r][c]
                above = self.sumMat[r][c + 1]
                self.sumMat[r + 1][c + 1] = prefix + above

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        row1, col1, row2, col2 = row1 + 1, col1 + 1, row2 + 1, col2 + 1
        bottomRight = self.sumMat[row2][col2]
        above = self.sumMat[row1 - 1][col2]
        left = self.sumMat[row2][col1 - 1]
        topLeft = self.sumMat[row1 - 1][col1 - 1]
        return bottomRight - above - left + topLeft

public class NumMatrix {

    private int[][] sumMat;

    public NumMatrix(int[][] matrix) {
        int ROWS = matrix.length, COLS = matrix[0].length;
        sumMat = new int[ROWS + 1][COLS + 1];

        for (int r = 0; r < ROWS; r++) {
            int prefix = 0;
            for (int c = 0; c < COLS; c++) {
                prefix += matrix[r][c];
                int above = sumMat[r][c + 1];
                sumMat[r + 1][c + 1] = prefix + above;
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        row1++; col1++; row2++; col2++;
        int bottomRight = sumMat[row2][col2];
        int above = sumMat[row1 - 1][col2];
        int left = sumMat[row2][col1 - 1];
        int topLeft = sumMat[row1 - 1][col1 - 1];
        return bottomRight - above - left + topLeft;
    }
}

class NumMatrix {
private:
    vector<vector<int>> sumMat;

public:
    NumMatrix(vector<vector<int>>& matrix) {
        int ROWS = matrix.size(), COLS = matrix[0].size();
        sumMat = vector<vector<int>>(ROWS + 1, vector<int>(COLS + 1, 0));

        for (int r = 0; r < ROWS; r++) {
            int prefix = 0;
            for (int c = 0; c < COLS; c++) {
                prefix += matrix[r][c];
                int above = sumMat[r][c + 1];
                sumMat[r + 1][c + 1] = prefix + above;
            }
        }
    }

    int sumRegion(int row1, int col1, int row2, int col2) {
        row1++; col1++; row2++; col2++;
        int bottomRight = sumMat[row2][col2];
        int above = sumMat[row1 - 1][col2];
        int left = sumMat[row2][col1 - 1];
        int topLeft = sumMat[row1 - 1][col1 - 1];
        return bottomRight - above - left + topLeft;
    }
};

class NumMatrix {
    /**
     * @param {number[][]} matrix
     */
    constructor(matrix) {
        const ROWS = matrix.length,
            COLS = matrix[0].length;
        this.sumMat = Array.from({ length: ROWS + 1 }, () =>
            Array(COLS + 1).fill(0),
        );

        for (let r = 0; r < ROWS; r++) {
            let prefix = 0;
            for (let c = 0; c < COLS; c++) {
                prefix += matrix[r][c];
                const above = this.sumMat[r][c + 1];
                this.sumMat[r + 1][c + 1] = prefix + above;
            }
        }
    }

    /**
     * @param {number} row1
     * @param {number} col1
     * @param {number} row2
     * @param {number} col2
     * @return {number}
     */
    sumRegion(row1, col1, row2, col2) {
        row1++;
        col1++;
        row2++;
        col2++;
        const bottomRight = this.sumMat[row2][col2];
        const above = this.sumMat[row1 - 1][col2];
        const left = this.sumMat[row2][col1 - 1];
        const topLeft = this.sumMat[row1 - 1][col1 - 1];
        return bottomRight - above - left + topLeft;
    }
}

public class NumMatrix {
    private int[,] sumMat;

    public NumMatrix(int[][] matrix) {
        int ROWS = matrix.Length;
        int COLS = matrix[0].Length;
        sumMat = new int[ROWS + 1, COLS + 1];

        for (int r = 0; r < ROWS; r++) {
            int prefix = 0;
            for (int c = 0; c < COLS; c++) {
                prefix += matrix[r][c];
                int above = sumMat[r, c + 1];
                sumMat[r + 1, c + 1] = prefix + above;
            }
        }
    }

    public int SumRegion(int row1, int col1, int row2, int col2) {
        row1++; col1++; row2++; col2++;
        int bottomRight = sumMat[row2, col2];
        int above = sumMat[row1 - 1, col2];
        int left = sumMat[row2, col1 - 1];
        int topLeft = sumMat[row1 - 1, col1 - 1];
        return bottomRight - above - left + topLeft;
    }
}

type NumMatrix struct {
    sumMat [][]int
}

func Constructor(matrix [][]int) NumMatrix {
    rows, cols := len(matrix), len(matrix[0])
    sumMat := make([][]int, rows+1)
    for i := range sumMat {
        sumMat[i] = make([]int, cols+1)
    }

    for r := 0; r < rows; r++ {
        prefix := 0
        for c := 0; c < cols; c++ {
            prefix += matrix[r][c]
            above := sumMat[r][c+1]
            sumMat[r+1][c+1] = prefix + above
        }
    }

    return NumMatrix{sumMat: sumMat}
}

func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
    row1++; col1++; row2++; col2++
    bottomRight := this.sumMat[row2][col2]
    above := this.sumMat[row1-1][col2]
    left := this.sumMat[row2][col1-1]
    topLeft := this.sumMat[row1-1][col1-1]
    return bottomRight - above - left + topLeft
}

class NumMatrix(matrix: Array<IntArray>) {
    private val sumMat: Array<IntArray>

    init {
        val rows = matrix.size
        val cols = matrix[0].size
        sumMat = Array(rows + 1) { IntArray(cols + 1) }

        for (r in 0 until rows) {
            var prefix = 0
            for (c in 0 until cols) {
                prefix += matrix[r][c]
                val above = sumMat[r][c + 1]
                sumMat[r + 1][c + 1] = prefix + above
            }
        }
    }

    fun sumRegion(row1: Int, col1: Int, row2: Int, col2: Int): Int {
        val r1 = row1 + 1
        val c1 = col1 + 1
        val r2 = row2 + 1
        val c2 = col2 + 1
        val bottomRight = sumMat[r2][c2]
        val above = sumMat[r1 - 1][c2]
        val left = sumMat[r2][c1 - 1]
        val topLeft = sumMat[r1 - 1][c1 - 1]
        return bottomRight - above - left + topLeft
    }
}

class NumMatrix {
    private var sumMat: [[Int]]

    init(_ matrix: [[Int]]) {
        let rows = matrix.count
        let cols = matrix[0].count
        sumMat = Array(repeating: Array(repeating: 0, count: cols + 1), count: rows + 1)

        for r in 0..<rows {
            var prefix = 0
            for c in 0..<cols {
                prefix += matrix[r][c]
                let above = sumMat[r][c + 1]
                sumMat[r + 1][c + 1] = prefix + above
            }
        }
    }

    func sumRegion(_ row1: Int, _ col1: Int, _ row2: Int, _ col2: Int) -> Int {
        let r1 = row1 + 1, c1 = col1 + 1, r2 = row2 + 1, c2 = col2 + 1
        let bottomRight = sumMat[r2][c2]
        let above = sumMat[r1 - 1][c2]
        let left = sumMat[r2][c1 - 1]
        let topLeft = sumMat[r1 - 1][c1 - 1]
        return bottomRight - above - left + topLeft
    }
}

Time & Space Complexity

Time complexity: $O(1)$ for each query.
Space complexity: $O(m * n)$

Where $m$ is the number of rows and $n$ is the number of columns in the matrix.

Common Pitfalls

Forgetting the Inclusion-Exclusion Principle

When computing the sum of a rectangular region using 2D prefix sums, you must subtract the regions above and to the left, then add back the top-left corner that was subtracted twice. The formula is bottomRight - above - left + topLeft. Forgetting to add back the top-left corner results in under-counting, while forgetting to subtract either the above or left region causes over-counting.

Off-by-One Errors with Prefix Sum Indices

The prefix sum matrix is typically sized (rows + 1) x (cols + 1) to handle edge cases where the query starts at row 0 or column 0. Mixing up whether indices are 0-based or 1-based leads to accessing wrong cells or out-of-bounds errors. When querying sumRegion(row1, col1, row2, col2), remember to shift indices appropriately when accessing the prefix sum matrix.

Building Prefix Sum Matrix Incorrectly

The 2D prefix sum at position (r, c) should represent the sum of all elements from (0, 0) to (r-1, c-1). A common mistake is computing prefix sums row by row without properly incorporating the contribution from previous rows. The correct formula is prefix[r+1][c+1] = matrix[r][c] + prefix[r][c+1] + prefix[r+1][c] - prefix[r][c], or equivalently, accumulate row prefix and add the cell directly above.