304. Range Sum Query 2D - Immutable

Problem Description

Given a 2D matrix matrix, implement the NumMatrix class to handle multiple queries. Each query calculates the sum of elements within a specified rectangular region defined by its top-left and bottom-right corners. The sumRegion method should have O(1) time complexity.

Solution: Two-Dimensional Prefix Sum

This solution leverages the concept of a two-dimensional prefix sum. A prefix sum array s stores the cumulative sum of elements up to a given row and column. By calculating the prefix sum array once during initialization, we can efficiently answer sum region queries in O(1) time.

Prefix Sum Formula:

The key to this approach is understanding how to calculate the sum of a rectangular region using the prefix sum array. The sum of a rectangle with top-left corner (row1, col1) and bottom-right corner (row2, col2) is given by:

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

Algorithm:

1. Initialization (__init__ or constructor):

   • Create a prefix sum array s with dimensions one larger than the input matrix matrix. This allows for easier indexing starting from 1.
   • Initialize s[0][j] and s[i][0] to 0 for all valid i and j.
   • Iterate through the input matrix. For each element matrix[i][j], calculate the prefix sum: s[i + 1][j + 1] = s[i + 1][j] + s[i][j + 1] - s[i][j] + matrix[i][j]
   • This formula ensures the cumulative sum includes the current element and avoids double-counting of previous sub-rectangles.

2. Query (sumRegion):

   • Given row1, col1, row2, and col2, directly apply the prefix sum formula to obtain the region's sum.

Time and Space Complexity:

• Time Complexity:
  • Initialization: O(m * n), where 'm' and 'n' are the dimensions of the matrix.
  • sumRegion query: O(1)
• Space Complexity: O(m * n) to store the prefix sum array.

Code Implementation

The following code demonstrates the solution in various programming languages:

Python:

class NumMatrix:
    def __init__(self, matrix: List[List[int]]):
        m, n = len(matrix), len(matrix[0])
        self.s = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(m):
            for j in range(n):
                self.s[i + 1][j + 1] = self.s[i + 1][j] + self.s[i][j + 1] - self.s[i][j] + matrix[i][j]
 
    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        return self.s[row2 + 1][col2 + 1] - self.s[row2 + 1][col1] - self.s[row1][col2 + 1] + self.s[row1][col1]
 

Java:

class NumMatrix {
    private int[][] s;
 
    public NumMatrix(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        s = new int[m + 1][n + 1];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                s[i + 1][j + 1] = s[i + 1][j] + s[i][j + 1] - s[i][j] + matrix[i][j];
            }
        }
    }
 
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return s[row2 + 1][col2 + 1] - s[row2 + 1][col1] - s[row1][col2 + 1] + s[row1][col1];
    }
}

(Other languages like C++, JavaScript, Go, TypeScript, Kotlin, and Rust would follow a similar structure, adapting the syntax and data structures accordingly.)

This detailed explanation and code examples should help you understand the solution to this LeetCode problem effectively. Remember that the key is the efficient pre-computation of the prefix sum array to enable O(1) query time.