Domain 2MediumCORE

Range Sum Query 2D - Immutable

We are given a static 2D integer matrix where no updates occur after initialization (Immutable). We need to support two operations: initializing the object with the grid data, and answering range sum queries for any rectangular sub-region defined by top-left (row1, col1) and bottom-right (row2, col2).

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Dynamic Programming

304. Range Sum Query 2D - Immutable

Model: qwen3.5:9b
Topics: Dynamic Programming
FAANG asked: 1
Acceptance rate: 41.1%


Problem Breakdown

We are given a static 2D integer matrix where no updates occur after initialization (Immutable). We need to support two operations: initializing the object with the grid data, and answering range sum queries for any rectangular sub-region defined by top-left (row1, col1) and bottom-right (row2, col2).

Inputs:

  • matrix: A 2D list of integers.
  • Query parameters: row1, col1 (top-left), row2, col2 (bottom-right).

Outputs:

  • Integer sum for the specified region.

Constraints & Edge Cases:

  • Matrix dimensions up to 200×200200 \times 200.
  • Values range from −105-10^5 to 10510^5, meaning sums can be negative or large, but Python handles arbitrary precision integers automatically (no overflow issues).
  • Queries are frequent (10410^4 calls), implying we need an efficient query time. The matrix is immutable, so precomputation during initialization is acceptable and expected.

Intuition

If I were to calculate the sum for every sumRegion call by iterating through each cell in the rectangle, what would happen? For a single query, that takes O((row2−row1)×(col2−col1))O((row2 - row1) \times (col2 - col1)), which simplifies to worst-case O(m⋅n)O(m \cdot n) per query. With up to 10410^4 queries and matrix size 200x200, the total operations would be roughly 4×1084 \times 10^8. This risks a Time Limit Exceeded (TLE).

Since the data is immutable, we can trade initialization time for faster query times. The standard technique for range sum queries in static grids is Prefix Sums (also known as Cumulative Sum or Integral Image).

The key insight: If I know the cumulative sum from (0, 0) to any point (i, j), I can derive the sum of any sub-rectangle using the inclusion-exclusion principle. Specifically, a rectangle’s sum is equal to the total area up to its bottom-right corner minus the areas above and left that are not part of our target region, plus back the intersection we subtracted twice (the top-left corner).

Approach

  1. Precomputation (__init__): Create a new matrix prefixSum with dimensions (m+1)×(n+1)(m+1) \times (n+1) initialized to zeros. The extra row and column handle boundary conditions where indices might be -1 conceptually, avoiding index checks during queries.
  2. Filling the Prefix Array: Iterate through each cell (i, j) of the original matrix. For prefixSum[i+1][j+1], calculate it as: matrix[i][j]+prefixSum[i][j+1]+prefixSum[i+1][j]−prefixSum[i][j]\text{matrix}[i][j] + \text{prefixSum}[i][j+1] + \text{prefixSum}[i+1][j] - \text{prefixSum}[i][j] This adds the current cell value, plus sums from above and left neighbors. We subtract prefixSum[i][j] because it was added twice (once via top neighbor, once via left neighbor).
  3. Query (sumRegion): Use the inclusion-exclusion formula on our precomputed array: result=P[row2+1][col2+1]−P[row1][col2+1]−P[row2+1][col1]+P[row1][col1]\text{result} = P[row2+1][col2+1] - P[row1][col2+1] - P[row2+1][col1] + P[row1][col1]
  4. Return: Return the calculated integer sum immediately in O(1)O(1) time.

Complexity Analysis

  • Time Complexity (Init): O(m⋅n)O(m \cdot n) to build the prefix array where mm is rows and nn is columns.
  • Space Complexity: O(m⋅n)O(m \cdot n) for storing the prefixSum matrix.
  • Query Time: O(1)O(1). This allows us to handle up to QQ queries in total time of O(Q+m⋅n)O(Q + m \cdot n), which fits well within limits given constraints (2002=40,000200^2 = 40,000, 10410^4 queries).

Solution

class NumMatrix:
    def __init__(self, matrix):
        if not matrix or not matrix[0]:
            self.P = []
            return
        
        m, n = len(matrix), len(matrix[0])
        # Use (m+1) x (n+1) to handle boundary conditions cleanly without index checks.
        # P[i][j] stores sum of rectangle from (0,0) to matrix[i-1][j-1].
        self.P = [[0] * (n + 1) for _ in range(m + 1)]

        for i in range(m):
            for j in range(n):
                # Accumulate current cell value and add prefix sums from top/left.
                # Subtract diagonal to correct double counting of the overlap region.
                self.P[i+1][j+1] = matrix[i][j] + \
                                   self.P[i][j+1] + \
                                   self.P[i+1][j] - \
                                   self.P[i][j]

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        # Inclusion-Exclusion Principle on the prefix array.
        # Note indices are shifted by +1 because of our padding in __init__.
        return (self.P[row2+1][col2+1] 
                - self.P[row1][col2+1] 
                - self.P[row2+1][col1] 
                + self.P[row1][col1])

Edge Cases Handled

  • Boundary Rectangles: When row1=0 or col1=0, the logic relies on row/col index 0 in our padded array (which is initialized to 0), correctly subtracting nothing from that side.
  • Single Cell Query: If (row2, col2) == (row1, col1), the formula still holds mathematically as it calculates a single cell sum via prefix differences.
  • Negative Values: The arithmetic logic handles negative integers naturally without special casing for signs.
  • Empty Matrix Check: Added an explicit check in __init__ to handle cases where input matrix is empty, though constraints say m,n≥1m,n \ge 1.