304. Range Sum Query 2D - Immutable

Problem Statement

link: LeetCode.cn LeetCode

Given a 2D matrix matrix, handle multiple queries of the following type:

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). Implement the NumMatrix class:

NumMatrix(int[][] matrix) Initializes the object with the integer matrix matrix. int sumRegion(int row1, int col1, int row2, int col2) Returns the sum of the elements of matrix inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2). You must design an algorithm where sumRegion works on O(1) time complexity.

Example:

Input: ["NumMatrix", "sumRegion", "sumRegion", "sumRegion"] [[[[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]]], [2, 1, 4, 3], [1, 1, 2, 2], [1, 2, 2, 4]] Output: [null, 8, 11, 12]

Solution Approach

The solution utilizes prefix sums to efficiently compute the sum of elements within a given rectangular region in constant time complexity (O(1)).

Algorithm

1. Initialization: Initialize a prefix sum matrix where each cell stores the sum of elements from the top-left corner of the original matrix to the corresponding cell. This step involves iterating over the original matrix and computing cumulative sums row by row.

2. Sum Calculation: For the sumRegion method, calculate the sum of the elements within a given rectangular region using the prefix sum matrix. This involves using the formula pre_sums[row2 + 1][col2 + 1] - pre_sums[row2 + 1][col1] - pre_sums[row1][col2 + 1] + pre_sums[row1][col1], where pre_sums represents the prefix sum matrix.

3. Optimization: By precomputing the prefix sums, the algorithm achieves constant time complexity for each query operation, making it efficient even for multiple queries on the same matrix.

Implement

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

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


    
       

    
    

Twitter  facebook  Email