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 .
- Values range from to , meaning sums can be negative or large, but Python handles arbitrary precision integers automatically (no overflow issues).
- Queries are frequent ( 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 , which simplifies to worst-case per query. With up to queries and matrix size 200x200, the total operations would be roughly . 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
- Precomputation (
__init__): Create a new matrixprefixSumwith dimensions initialized to zeros. The extra row and column handle boundary conditions where indices might be -1 conceptually, avoiding index checks during queries. - Filling the Prefix Array: Iterate through each cell
(i, j)of the original matrix. ForprefixSum[i+1][j+1], calculate it as: This adds the current cell value, plus sums from above and left neighbors. We subtractprefixSum[i][j]because it was added twice (once via top neighbor, once via left neighbor). - Query (
sumRegion): Use the inclusion-exclusion formula on our precomputed array: - Return: Return the calculated integer sum immediately in time.
Complexity Analysis
- Time Complexity (Init): to build the prefix array where is rows and is columns.
- Space Complexity: for storing the
prefixSummatrix. - Query Time: . This allows us to handle up to queries in total time of , which fits well within limits given constraints (, 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=0orcol1=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 .