Range Sum Query 2D - Immutable

The problem requires us to perform multiple queries to find the sum of elements in a specific rectangle inside a 2D matrix. The challenge here is to design the solution in such a way that each query operates in ( O(1) ) time complexity.

To achieve this, we can precompute the prefix sum for each cell (i, j), which includes the sum of all cells above and to the left of it. We can then utilize this information to calculate the sum of any rectangle within the matrix in constant time.

Here’s a step-by-step explanation of the solution:

  1. Precompute the Prefix Sum: Compute a new matrix prefixSum of the same size, where prefixSum[i][j] contains the sum of the elements from matrix[0][0] to matrix[i][j].

  2. Calculate the Sum of a Specific Rectangle: To get the sum of elements inside the rectangle defined by (row1, col1) and (row2, col2), we can use the following formula: [ \text{sum} = \text{prefixSum}[row2][col2] - \text{prefixSum}[row1 - 1][col2] - \text{prefixSum}[row2][col1 - 1] + \text{prefixSum}[row1 - 1][col1 - 1] ]

Here’s the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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

        # Calculate prefix sum
        for i in range(m):
            for j in range(n):
                self.prefixSum[i + 1][j + 1] = matrix[i][j] + self.prefixSum[i][j + 1] + self.prefixSum[i + 1][j] - self.prefixSum[i][j]

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

By precomputing the prefix sum, the sumRegion method can perform each query in constant time, i.e., ( O(1) ).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

class NumMatrix

=begin
    :type matrix: Integer[][]
=end
    def initialize(matrix)
        rows = matrix.length
        cols = matrix[0].length rescue 0
        if rows == 0 || cols == 0 
            return
        end
        @dp = Array.new(rows) { Array.new(cols+1, 0)}
        for row in (0..rows-1) 
           for col in (0..cols-1)
              @dp[row][col+1] = @dp[row][col] + matrix[row][col] 
           end
        end
    end

=begin
    :type row1: Integer
    :type col1: Integer
    :type row2: Integer
    :type col2: Integer
    :rtype: Integer
=end
    def sum_region(row1, col1, row2, col2)
        sum = 0
        for row in (row1..row2)
           sum += @dp[row][col2+1] - @dp[row][col1] 
        end
        sum
    end
end

# Your NumMatrix object will be instantiated and called as such:
# obj = NumMatrix.new(matrix)
# param_1 = obj.sum_region(row1, col1, row2, col2)