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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Range Sum Query 2D - Immutable

Number: 304

Difficulty: Medium

Paid? No

Companies: Meta, Bloomberg, Microsoft, Google, Amazon, Lyft

Problem Description

You are given a 2D matrix and need to answer multiple queries asking for the sum of a submatrix defined by its upper left and lower right corners. The task is to design a solution where each query runs in O(1) time.

Key Insights

  • Precompute a prefix sum matrix where each cell accumulates the sum of elements above and to the left.
  • Use the inclusion-exclusion principle to efficiently calculate the sum of any submatrix using precomputed sums.
  • Preprocessing the matrix takes O(m * n) time, but each query is answered in constant time (O(1)).

Space and Time Complexity

Time Complexity:

  • Preprocessing: O(m * n)
  • Each Query: O(1)

Space Complexity: O(m * n) for storing the prefix sum matrix.

Solution

The solution involves building a prefix sum matrix, dp, where dp[i+1][j+1] holds the sum of elements in the submatrix from (0, 0) to (i, j). This allows summing any rectangular region using the inclusion-exclusion principle. Specifically, for a query defined by (row1, col1) to (row2, col2), the region sum can be computed as:

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

This approach ensures that after an O(m * n) preprocessing step, each query is computed in constant time.

Code Solutions

Below are the code solutions in Python, JavaScript, C++, and Java with line-by-line comments.

# Class definition for NumMatrix using prefix sum 2D array.
class NumMatrix:
    def __init__(self, matrix):
        # Get dimensions of the matrix.
        m = len(matrix)
        n = len(matrix[0]) if m > 0 else 0
        # Create prefix sum matrix with extra row and column.
        self.dp = [[0] * (n + 1) for _ in range(m + 1)]
        # Precompute the prefix sum values.
        for i in range(m):
            for j in range(n):
                # Sum of current cell, top, left, and subtract overlapping top-left.
                self.dp[i+1][j+1] = self.dp[i][j+1] + self.dp[i+1][j] - self.dp[i][j] + matrix[i][j]

    def sumRegion(self, row1, col1, row2, col2):
        # Calculate the sum using the inclusion-exclusion principle.
        return self.dp[row2+1][col2+1] - self.dp[row1][col2+1] - self.dp[row2+1][col1] + self.dp[row1][col1]
← Back to All Questions