NeetCode #100LC-304MediumArrays & HashingNC 250
← Back to All Problems#100 · #304 · Range Sum Query 2D - Immutable(二维区域和检索 - 矩阵不可变)
📌 Problem Statement & Constraints
Design a data structure that answers rectangle-sum queries on an immutable 2D matrix. Implement
NumMatrix(matrix) and sumRegion(row1, col1, row2, col2), where the query returns the sum of the submatrix with those inclusive corner coordinates. Constraints: 1 <= m, n <= 200; -10^4 <= matrix[i][j] <= 10^4; up to 10^4 queries.💡 Core Algorithmic Approaches
- A per-query brute force is O(m*n), which is too slow with 10^4 queries. Precompute so each query is O(1).
- Build a 2D prefix sum
Pof size(m+1) x (n+1), whereP[i+1][j+1]is the sum of the submatrixmatrix[0..i][0..j]. - Recurrence:
P[i+1][j+1] = P[i][j+1] + P[i+1][j] - P[i][j] + matrix[i][j]. The subtraction removes the double-counted top-left block. - Query with inclusion-exclusion:
P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]. The extra padding row/column eliminates all boundary special cases.
💻 Benchmark Python3 Implementation
class NumMatrix:
def __init__(self, matrix: List[List[int]]):
m, n = len(matrix), len(matrix[0])
# P[i+1][j+1] = sum of matrix[0..i][0..j]; the extra row/col avoids edge cases
self.P = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m):
for j in range(n):
self.P[i + 1][j + 1] = (self.P[i][j + 1] + self.P[i + 1][j]
- self.P[i][j] + matrix[i][j])
def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
return (self.P[row2 + 1][col2 + 1]
- self.P[row1][col2 + 1]
- self.P[row2 + 1][col1]
+ self.P[row1][col1])⚡ Complexity Deep Dive
⏱️ Time Complexity
O(m*n) to build the prefix table, then O(1) per query. The brute-force alternative is O(m*n) per query, i.e. O(q*m*n) overall.
💾 Space Complexity
O(m*n) for the prefix table. The (m+1) x (n+1) padding costs one extra row and column but removes all boundary handling.
⚠️ Interview Pitfalls & Follow-ups
- Getting the inclusion-exclusion signs wrong: it is
+ P[r1][c1]at the end, because the top-left block is subtracted twice. Sketch the four rectangles to verify. - Omitting the padding row/column: without it,
row1 == 0orcol1 == 0requires separate branches, which is where bugs live. - Using 1-based indexing in the query: the API is 0-based, so the
+1offsets are mandatory. - Assuming the matrix is square: rows and columns have independent bounds; use
mandnseparately.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.