Leetcode 304. Range Sum Query 2D - Immutable

Problem Explanation

Let's try to frame the problem in simpler words.

We are given a matrix, which is a two-dimensional array. We are asked to write a function called sumRegion(row1, col1, row2, col2) which calculates the sum of elements present inside a rectangle within the matrix. The rectangle is defined by points (row1, col1) and (row2, col2).

Here, (row1, col1) signifies the upper left corner and (row2, col2) signifies lower right corner of the rectangle.

Let's understand this better with an example:

1
2
3matrix = [
4  [3, 0, 1, 4, 2],
5  [5, 6, 3, 2, 1],
6  [1, 2, 0, 1, 5],
7  [4, 1, 0, 1, 7],
8  [1, 0, 3, 0, 5]
9]

If you call sumRegion(2, 1, 4, 3), we are required to calculate the sum of elements inside rectangle formed by points (2,1) and (4,3). So, the rectangle will include elements 2, 0, 1, 1, 0, 1, 0, 3 which add up to 8.

Solution Approach

We will be using a technique of prefix sum to efficiently sum the elements in a rectangle.

We first calculate a 2D prefix sum matrix such that each cell in this matrix represents the sum of values in the matrix up to the point at that cell i.e if original matrix is M and prefix matrix is P, P[i][j] is sum of all elements in sub-matrix from (0,0) to (i,j) in M.

This is done by add the current cell value M[i][j], the prefix sum till previous row P[i-1][j], the prefix sum till previous column P[i][j-1] and subtract the prefix sum to the previous diagonal cell P[i-1][j-1].

1
2
3P[i][j] = M[i][j] + P[i-1][j] + P[i][j-1] - P[i-1][j-1]

To find the sum of the rectangle region (row1, col1) to (row2, col2), we sum the prefix sum till (row2,col2) and (row1-1, col1-1) (diagonal of rectangle outside), subtract the prefix sums till (row1-1, col2) and (row2, col1-1) (overlapping areas).

1
2
3 sum = P[row2][col2] - P[row2][col1-1] - P[row1-1][col2] + P[row1-1][col1-1]

C++ Solution

1
2cpp
3class NumMatrix {
4public:
5    vector<vector<int>> prefix;
6    NumMatrix(vector<vector<int>>& matrix) {
7        int m = matrix.size();
8        int n = m > 0 ? matrix[0].size() : 0;
9        prefix = vector<vector<int>>(m + 1, vector<int>(n + 1, 0));
10        for (int i = 0; i < m; i++) {
11            for (int j = 0; j < n; j++) {
12                prefix[i + 1][j + 1] = matrix[i][j] + prefix[i][j + 1] + prefix[i + 1][j] - prefix[i][j];
13            }
14        }
15    }
16    
17    int sumRegion(int row1, int col1, int row2, int col2) {
18        return prefix[row2 + 1][col2 + 1] - prefix[row1][col2 + 1] - prefix[row2 + 1][col1] + prefix[row1][col1];
19    }
20};

Java Solution

1
2java
3class NumMatrix {
4    private int[][] prefix;
5    
6    public NumMatrix(int[][] matrix) {
7        if (matrix.length == 0 || matrix[0].length == 0) return;
8        int m = matrix.length, n = matrix[0].length;
9        prefix = new int[m + 1][n + 1];
10        for (int i = 0; i < m; i++) {
11            for (int j = 0; j < n; j++) {
12                prefix[i + 1][j + 1] = matrix[i][j] + prefix[i][j + 1] + prefix[i + 1][j] - prefix[i][j];
13            }
14        }
15    }
16    
17    public int sumRegion(int row1, int col1, int row2, int col2) {
18        return prefix[row2 + 1][col2 + 1] - prefix[row1][col2 + 1] - prefix[row2 + 1][col1] + prefix[row1][col1];
19    }
20}

Python Solution

1
2python
3class NumMatrix:
4
5    def __init__(self, matrix):
6        if not matrix:
7            return
8        m, n = len(matrix), len(matrix[0])
9        self.prefix = [[0] * (n + 1) for _ in range(m + 1)]
10        for i in range(m):
11            for j in range(n):
12                self.prefix[i + 1][j + 1] = matrix[i][j] + self.prefix[i][j + 1] + self.prefix[i + 1][j] - self.prefix[i][j]
13
14    def sumRegion(self, row1, col1, row2, col2) -> int:
15        return self.prefix[row2 + 1][col2 + 1] - self.prefix[row1][col2 + 1] - self.prefix[row2 + 1][col1] + self.prefix[row1][col1]

JavaScript Solution

1
2javascript
3class NumMatrix {
4    constructor(matrix) {
5        if (!matrix.length || !matrix[0].length) return;
6        const m = matrix.length, n = matrix[0].length;
7        this.prefix = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
8        for (let i = 0; i < m; i++) {
9        for (let j = 0; j < n; j++) {
10            this.prefix[i + 1][j + 1] = matrix[i][j] + this.prefix[i][j + 1] + this.prefix[i + 1][j] - this.prefix[i][j];
11        }
12    }
13    
14    sumRegion(row1, col1, row2, col2) {
15        return this.prefix[row2 + 1][col2 + 1] - this.prefix[row1][col2 + 1] - this.prefix[row2 + 1][col1] + this.prefix[row1][col1];
16    }
17}
18

C# Solution

1
2csharp
3public class NumMatrix {
4    private int[][] prefix;
5    public NumMatrix(int[][] matrix) {
6        if (matrix == null || matrix.Length == 0 || matrix[0].Length == 0) return;
7        int m = matrix.Length, n = matrix[0].Length;
8        prefix = new int[m + 1][];
9        for (int i = 0; i <= m; i++)
10        {
11            prefix[i] = new int[n + 1];
12        }
13        
14        for (int i = 0; i < m; i++) {
15            for (int j = 0; j < n; j++) {
16                prefix[i + 1][j + 1] = matrix[i][j] + prefix[i][j + 1] + prefix[i + 1][j] - prefix[i][j];
17            }
18        }
19    }
20    
21    public int SumRegion(int row1, int col1, int row2, int col2) {
22        return prefix[row2 + 1][col2 + 1] - prefix[row1][col2 + 1] - prefix[row2 + 1][col1] + prefix[row1][col1];
23    }
24}

The solution is now provided in five popular programming languages: C++, Java, Python, JavaScript and C#. Each solution utilizes a prefix sum matrix to efficiently calculate the sum of values in a rectangular region within the given matrix.

The constructors or initialization functions in each language create the prefix sum matrix based on the input matrix. By iterating over the input matrix cells, each cell in the prefix sum matrix is computed as the sum of the current input matrix cell, the prefix sum cell from the previous row, the prefix sum cell from the previous column, and the negative of the prefix sum cell from the previous diagonal.

The sumRegion function in each language calculates and returns the sum of the matrix values enclosed within the rectangle defined by its row and column index parameters. The sum is calculated as the sum of the prefix cell at the bottom-right corner of the rectangle and the prefix cell outside the rectangle's top-left corner, subtracted by the prefix cells outside the rectangle's right-edge and the prefix cells outside the rectangle's bottom-edge.

The time complexity for constructing the prefix sum matrix of a given M x N matrix is O(MN) and the time complexity for calculating the sum of a rectangular region using the prefix sum matrix is O(1). Thus, the sumRegion function will always execute in constant time regardless of the size of the rectangular region. These solutions are optimal for repeated sumRegion queries on the same matrix.