Range Query sum of elements in a submatrix

Hard

📘 Problem Statement

Given a 2D matrix matrix 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). The query should return answer in \(O(1)\) time complexity.

🔍 Example

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

obj = NumMatrix(matrix)
print(obj.sumRegion(1, 1, 2, 2))  # Output: 11
print(obj.sumRegion(2, 1, 3, 3))  # Output: 6

---

🛠️ Solution

This problem can be solved using a PrefixSum of a matrix. Our prefixSum matrix P, where P[i+1][j+1] holds the sum of the submatrix from the top-left corner (0, 0) to (i, j) of the original matrix A.

To do this, we create a matrix with one extra row and column, initialized with zeros:

Dimensions: If A is m x n, P is (m+1) x (n+1)

---

✨ Algorithm Steps

To compute PrefixSum of the given matrix from (0,0) to (i, j), the idea is based on Inclusion / Exclusion where the prefix sum upto (i,j) will be :

Full matrix up to (i,j):


  +-----------+---------+
  |           |         |
  |  A        |   B     |
  |           |         |
  +-----------+---------+
  |           | (i,j)
  |  C        |  D (A[i][j])
  +-----------+---------+

• P[i][j+1] includes regions A + B
• P[i+1][j] includes A + C
• So when you add both: (A+B) + (A+C) = 2A + B + C
• But you only want A + B + C + D (i.e., full area)
• So subtract A once: P[i-1][j-1]

This leads to our prefix formula for index (i,j) as follows :

P[i+1][j+1] = P[i][j+1]+P[i+1][j]−P[i][j]+A[i−1][j−1]

Now, to vend out the sum of submatrix from index (row1, col1) to (row2, col2) in \(O(1)\) complexity, we use the similar logic.

✅ Start with P[r2+1][c2+1] → covers entire region including submatrix X and extras.

❌ Subtract P[r1][c2+1] → removes the top strip above X

❌ Subtract P[r2+1][c1] → removes the left strip left of X

🚫 Now we’ve subtracted the top-left overlap area twice — once in each subtraction.

✅ So we must add it back: + P[r1][c1]

---

class NumMatrix:

    def __init__(self, matrix: List[List[int]]):

        self.prefix_matrix = self.create_prefix_matrix(matrix)
        
    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:

        # Add whole region from 0,0 to row2, col2
        # then subract top strip from 0,0 to row1 -1, col2
        # then subtract left strip from 0,0 to row2, col1-1]
        # Add overlap area between 0,0 and row1-1, col -1 since it was removed twice
        return (
            self.prefix_matrix[row2+1][col2+1] 
            - self.prefix_matrix[row1][col2+1]
            - self.prefix_matrix[row2+1][col1] 
            + self.prefix_matrix[row1][col1]
            )

    def create_prefix_matrix(self, matrix):
        row, col = len(matrix), len(matrix[0])

        prefix_matrix = [[ 0 for i in range(col + 1)] for j in range(row+1)]
        
        for i in range(row):
            for j in range(col):
                    prefix_matrix[i+1][j+1] = (
                        matrix[i][j] 
                        + prefix_matrix[i][j+1] 
                        + prefix_matrix[i+1][j] 
                        - prefix_matrix[i][j]
                    )
        return prefix_matrix

---

⏱️ Time & Space Complexity

• It takes \(O(m × n)\) to build the prefix sum matrix.
• To return range sum of a submatrix, our method returns sum in \(O(1)\) time.