We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Range Sum Query 2D - Immutable

Difficulty: Medium

Problem Description

Given a 2D matrix, handle multiple queries to calculate the sum of the elements inside a rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2). Implement the NumMatrix class with methods to initialize the matrix and perform sum queries efficiently.

Key Insights

  • Use a prefix sum array to preprocess the matrix, allowing for O(1) time complexity for sum queries.
  • The prefix sum array stores cumulative sums, where each element at (i, j) represents the sum of all elements in the matrix from (0, 0) to (i, j).
  • The sum of any submatrix can be computed using the inclusion-exclusion principle.

Space and Time Complexity

Time Complexity: O(m * n) for initialization, O(1) for each sumRegion query.
Space Complexity: O(m * n) for the prefix sum array.

Solution

To efficiently handle the sum queries, we use a prefix sum array. The prefix sum array is constructed such that each element at (i, j) contains the sum of all elements from the top-left corner (0, 0) to (i, j). For any query that asks for the sum of a submatrix defined by (row1, col1) and (row2, col2), we can compute it using the values from the prefix sum array with the inclusion-exclusion principle:

sumRegion(row1, col1, row2, col2) = prefix[row2][col2] - prefix[row1-1][col2] - prefix[row2][col1-1] + prefix[row1-1][col1-1]

This approach allows us to reduce the time complexity of each query to O(1) after an initial preprocessing step that takes O(m * n) time.

Code Solutions

class NumMatrix:
    def __init__(self, matrix):
        if not matrix:
            self.prefix_sum = []
            return
            
        self.rows, self.cols = len(matrix), len(matrix[0])
        self.prefix_sum = [[0] * self.cols for _ in range(self.rows)]
        
        for i in range(self.rows):
            for j in range(self.cols):
                self.prefix_sum[i][j] = matrix[i][j]
                if i > 0:
                    self.prefix_sum[i][j] += self.prefix_sum[i - 1][j]
                if j > 0:
                    self.prefix_sum[i][j] += self.prefix_sum[i][j - 1]
                if i > 0 and j > 0:
                    self.prefix_sum[i][j] -= self.prefix_sum[i - 1][j - 1]

    def sumRegion(self, row1, col1, row2, col2):
        total = self.prefix_sum[row2][col2]
        if row1 > 0:
            total -= self.prefix_sum[row1 - 1][col2]
        if col1 > 0:
            total -= self.prefix_sum[row2][col1 - 1]
        if row1 > 0 and col1 > 0:
            total += self.prefix_sum[row1 - 1][col1 - 1]
        return total
← Back to All Questions