Range Sum Query 2d Immutable - Leetcode Solution

Problem Statement:

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

Range Sum Query 2D - Immutable Example:

Given 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

Solution:

In this problem, we are given a 2D matrix, and we need to find the sum of the elements in the sub-matrix defined by the given upper left corner and lower right corner. The first approach that comes to mind is brute-force: just calculate the sum of all the elements in the sub-matrix, which would require O(m * n) time complexity, where m and n are the dimensions of the matrix. However, we can optimize this solution by precomputing the sums of all sub-matrices that start from the top-left corner of the matrix.

Let's create a 2D array called sum, where sum[i][j] stores the sum of all elements in the sub-matrix from (0,0) to (i,j) inclusive. To build this array, we can use dynamic programming. Specifically, we can calculate the value of sum[i][j] as follows:

sum[i][j] = matrix[i][j] + sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1]

The rationale behind this formula is that we can calculate the sum of any sub-matrix (i1,j1) to (i2,j2) by taking the sum of all elements from (0,0) to (i2,j2) and subtracting the sum of all elements from (0,0) to (i1-1,j2), (i2,j1-1), and (i1-1,j1-1). The last term is subtracted twice, so we add it back to get the correct sum.

Once we have built the sum array, we can find the sum of the sub-matrix (row1,col1) to (row2,col2) by using the formula:

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

This formula follows from the same rationale as before: we take the sum of all elements from (0,0) to (row2,col2) and subtract the sum of all elements from (0,0) to (row1-1,col2), (row2,col1-1), and (row1-1,col1-1). Again, the last term is subtracted twice, so we add it back.

Here is the Python code that implements this solution:

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

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

The init function calculates the sum array as explained earlier, while the sumRegion function uses the formula to find the sum of the sub-matrix.

Time Complexity: O(mn) for init, O(1) for sumRegion. Space Complexity: O(mn) for sum array.

1