⚡Flashcard Drill➔
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

  1. A per-query brute force is O(m*n), which is too slow with 10^4 queries. Precompute so each query is O(1).
  2. Build a 2D prefix sum P of size (m+1) x (n+1), where P[i+1][j+1] is the sum of the submatrix matrix[0..i][0..j].
  3. 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.
  4. 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 == 0 or col1 == 0 requires separate branches, which is where bugs live.
  • Using 1-based indexing in the query: the API is 0-based, so the +1 offsets are mandatory.
  • Assuming the matrix is square: rows and columns have independent bounds; use m and n separately.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems