Range Sum Query 2D Immutable
The briefingthe full drill, in my own words
The drill: Answer many rectangle-sum queries against a fixed 2D grid — the grid never changes after construction, only the query rectangles do.
A fixed 2D grid of integers is handed over once at construction, and after that only one kind of question ever gets asked: what does a given rectangle of that grid sum to?
The grid itself never changes after it's built — no updates, no insertions — only the query rectangles vary, arriving one at a time and each needing an answer.
A rectangle query names its top-left and bottom-right corners, inclusive on both ends, and expects back the sum of every cell inside that boundary.
- the grid can be up to a couple hundred rows and columns
- cell values may be negative, zero, or positive
- the grid is immutable after construction — queries only, no updates
- query rectangle corners are always valid, inclusive coordinates within the grid
The hintstake only what you need
HINT 1 THE NUDGE
Summing a rectangle by walking every cell inside it is correct, but if the grid gets asked about again and again, that walk repeats work every single time. What could you compute once, before the first query even arrives?
HINT 2 THE STRUCTURE
A running total from the top-left corner to any cell tells you the sum of that whole sub-rectangle in one lookup — build that table once at construction.
HINT 3 ONE STEP FROM THE ANSWER
sumRegion(r1,c1,r2,c2) = prefix[r2+1][c2+1] − prefix[r1][c2+1] − prefix[r2+1][c1] + prefix[r1][c1] — inclusion-exclusion adds the doubly-subtracted top-left corner back in.
Coach's boardthe pattern, step by step
matrix = [[1,2],[3,4]]. Build a prefix-sum table once, padded with a zero row and column.
The splitstwo paces, two languages
class NumMatrix:
def __init__(self, matrix: List[List[int]]):
rows = len(matrix)
cols = len(matrix[0]) if rows else 0
self.prefix = [[0] * (cols + 1) for _ in range(rows + 1)]
for r in range(rows):
for c in range(cols):
self.prefix[r + 1][c + 1] = (
matrix[r][c] + self.prefix[r][c + 1] + self.prefix[r + 1][c] - self.prefix[r][c]
)
def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
p = self.prefix
return p[row2 + 1][col2 + 1] - p[row1][col2 + 1] - p[row2 + 1][col1] + p[row1][col1]class NumMatrix:
def __init__(self, matrix: List[List[int]]):
self.grid = matrix
def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
total = 0
for r in range(row1, row2 + 1):
for c in range(col1, col2 + 1):
total += self.grid[r][c]
return totalclass NumMatrix {
private final int[][] prefix;
public NumMatrix(int[][] matrix) {
int rows = matrix.length;
int cols = rows > 0 ? matrix[0].length : 0;
prefix = new int[rows + 1][cols + 1];
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
prefix[r + 1][c + 1] = matrix[r][c] + prefix[r][c + 1] + prefix[r + 1][c] - prefix[r][c];
}
}
}
public int sumRegion(int row1, int col1, int row2, int col2) {
return prefix[row2 + 1][col2 + 1] - prefix[row1][col2 + 1] - prefix[row2 + 1][col1] + prefix[row1][col1];
}
}class NumMatrix {
private final int[][] grid;
public NumMatrix(int[][] matrix) {
this.grid = matrix;
}
public int sumRegion(int row1, int col1, int row2, int col2) {
int total = 0;
for (int r = row1; r <= row2; r++) {
for (int c = col1; c <= col2; c++) {
total += grid[r][c];
}
}
return total;
}
}✓ CHIP-TIMEDALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED