NUHMAN.com

Introduction

LeetCode 304: Range Sum Query 2D - Immutable asks us to design a data structure that allows us to efficiently compute the sum of elements in a submatrix defined by two indices (row1, col1) and (row2, col2) in a given immutable 2D integer matrix. The matrix is initialized at the beginning, and after that, we need to process multiple range sum queries. The goal is to optimize these range sum queries so that they are answered quickly.

We can use a 2D prefix sum technique to precompute the sum of elements in a submatrix. This allows for constant-time querying once the prefix sum array is built.

Problem Statement

Given a 2D matrix matrix where each element matrix[i][j] is an integer, implement a data structure that supports the following operation:

1. sumRegion(row1, col1, row2, col2): Return the sum of the elements of the submatrix from (row1, col1) to (row2, col2) inclusive.
2. Constructor(matrix): Initializes the data structure with the given 2D matrix matrix.

Example

python

# Example 1
Input: 
["NumMatrix", "sumRegion", "sumRegion", "sumRegion"]
[[[[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 1, 1, 4], [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, 1, 1, 4], [1, 0, 3, 0, 5]]);
# numMatrix.sumRegion(2, 1, 4, 3); -> return 8 ((1 + 2 + 0 + 1) + (4 + 1 + 1 + 1) + (1 + 0 + 3 + 0) = 8)
# numMatrix.sumRegion(1, 1, 2, 2); -> return 11 (6 + 3 + 2 + 0 = 11)
# numMatrix.sumRegion(1, 2, 2, 4); -> return 12 (3 + 2 + 0 + 1 + 5 = 12)

✅ Step-by-Step Solution

🧠 Intuition

To solve this problem efficiently, we can use the 2D prefix sum technique, which is an extension of the 1D prefix sum concept. The idea is to precompute the sum of all elements in the matrix up to each index (i, j) in a 2D array called prefix. This allows us to quickly calculate the sum of any submatrix.

The formula to calculate the sum of a submatrix from (row1, col1) to (row2, col2) using the prefix sum array is:

sumRegion(row1,col1,row2,col2)=prefix[row2+1][col2+1]−prefix[row1][col2+1]−prefix[row2+1][col1]+prefix[row1][col1]\text{sumRegion}(row1, col1, row2, col2) = \text{prefix}[row2 + 1][col2 + 1] - \text{prefix}[row1][col2 + 1] - \text{prefix}[row2 + 1][col1] + \text{prefix}[row1][col1]sumRegion(row1,col1,row2,col2)=prefix[row2+1][col2+1]−prefix[row1][col2+1]−prefix[row2+1][col1]+prefix[row1][col1]This formula essentially extracts the sum of elements in the desired submatrix using inclusion-exclusion.

✅ Approach

1. Initialization:

• Precompute a 2D prefix sum array where each element at (i, j) stores the sum of all elements in the matrix from (0, 0) to (i-1, j-1).

1. sumRegion Calculation:

• To calculate the sum of elements in the submatrix defined by (row1, col1) and (row2, col2), use the inclusion-exclusion principle based on the prefix array.

1. Optimization:

• The initialization of the prefix sum array takes O(m * n) time, where m is the number of rows and n is the number of columns in the matrix.
• Each query (sumRegion) takes O(1) time due to the precomputed prefix sum array.

✅ Python Code

python

class NumMatrix:

    def __init__(self, matrix: list[list[int]]):
        if not matrix:
            return
        
        # Initialize prefix sum array with dimensions (m+1) x (n+1)
        self.prefix = [[0] * (len(matrix[0]) + 1) for _ in range(len(matrix) + 1)]
        
        # Build the prefix sum array
        for i in range(1, len(matrix) + 1):
            for j in range(1, len(matrix[0]) + 1):
                self.prefix[i][j] = matrix[i - 1][j - 1] + self.prefix[i - 1][j] + self.prefix[i][j - 1] - self.prefix[i - 1][j - 1]

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        # Calculate the sum using the inclusion-exclusion principle
        return (self.prefix[row2 + 1][col2 + 1] 
                - self.prefix[row1][col2 + 1] 
                - self.prefix[row2 + 1][col1] 
                + self.prefix[row1][col1])

🧪 How It Works

1. Constructor:

• The NumMatrix class is initialized with a 2D matrix matrix.
• We then build the prefix sum array where each element at (i, j) stores the sum of all elements from (0, 0) to (i-1, j-1) in the matrix. This is done using dynamic programming in O(m * n) time, where m is the number of rows and n is the number of columns.

1. sumRegion Function:

• The sumRegion(row1, col1, row2, col2) function calculates the sum of elements in the submatrix from (row1, col1) to (row2, col2) using the prefix sum array.
• It uses the inclusion-exclusion principle to compute the sum efficiently in constant time O(1).

1. Efficiency:

• Initialization: The prefix sum array is built in O(m * n) time, where m is the number of rows and n is the number of columns in the matrix.
• Query: Each query (sumRegion) takes O(1) time due to the precomputed prefix sum array.

⏱️ Time and Space Complexity

MetricValueTime Complexity (Initialization)O(m * n)Time Complexity (sumRegion)O(1)Space ComplexityO(m * n)

• Time Complexity (Initialization): The time complexity for building the prefix sum array is O(m * n), where m is the number of rows and n is the number of columns in the matrix.
• Time Complexity (sumRegion): Each query is answered in constant time O(1) since it involves only a few lookups and arithmetic operations on the prefix sum array.
• Space Complexity: We need O(m * n) space to store the prefix sum array, where m is the number of rows and n is the number of columns in the matrix.

🔍 Edge Cases

1. Empty Matrix:

• If the input matrix is empty, we should handle it gracefully, and any query should return 0.

1. Single Row or Column Matrix:

• If the matrix has only one row or one column, the same approach applies, and queries will still be answered efficiently.

1. Multiple Queries:

• The sumRegion function should handle multiple queries efficiently, even if the matrix is large, since each query takes constant time after initialization.

✅ Conclusion

LeetCode 304: Range Sum Query 2D - Immutable is a problem that can be solved efficiently by utilizing the 2D prefix sum technique. By precomputing the prefix sums, we reduce the time complexity for each range sum query to O(1), making it optimal for large matrix sizes.

• The initialization of the prefix sum array takes O(m * n) time, and each sumRegion query is answered in O(1) time, making this approach highly efficient for multiple queries.

This solution is ideal when we need to process many range sum queries on an immutable 2D matrix.