Range Sum Query 2D Immutable

MEDIUM✓ CHIP-TIMEDLC #304 — FULL STATEMENT ↗

The drill: Answer many rectangle-sum queries against a fixed 2D grid — the grid never changes after construction, only the query rectangles do.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

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.

EX 01

NumMatrix([[2, -1, 4, 0], [3, 5, -2, 1], [0, 2, 3, -4], [1, 1, 2, 6]])

sumRegion(0, 0, 3, 3) → 23

sumRegion(1, 1, 2, 2) → 8

sumRegion(0, 0, 0, 0) → 2

sumRegion(3, 3, 3, 3) → 6

FULL GRID, A SUB-SQUARE, AND TWO SINGLE CELLS

EX 02

NumMatrix([[7]])

sumRegion(0, 0, 0, 0) → 7

1X1 MATRIX

EX 03

NumMatrix([[1, 2, 3, 4, 5]])

sumRegion(0, 0, 0, 4) → 15

sumRegion(0, 1, 0, 3) → 9

SINGLE ROW

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 HINTS — TAKE 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 BOARD — THE PATTERN, STEP BY STEP

THE RUNNING CORNERPATTERN · 2-D PREFIX SUMmatrix = [[1, 2], [3, 4]] · sumRegion(0,0,1,1)

STEP 1

matrix = [[1,2],[3,4]]. Build a prefix-sum table once, padded with a zero row and column.

STEP 1 / 7 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/range-sum-query-2d-immutable.py — RACE PACE

LANG ▸

PACE ▸

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]

TIME O(ROWS·COLS) BUILD, O(1) PER QUERYSPACE O(ROWS·COLS)PYTHON · RACE PACE · 14 LN

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 total

TIME O(1) BUILD, O(ROWS·COLS) PER QUERYSPACE O(ROWS·COLS)PYTHON · TRAINING PACE · 10 LN

class 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];
    }
}

TIME O(ROWS·COLS) BUILD, O(1) PER QUERYSPACE O(ROWS·COLS)JAVA · RACE PACE · 18 LN

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;
    }
}

TIME O(1) BUILD, O(ROWS·COLS) PER QUERYSPACE O(ROWS·COLS)JAVA · TRAINING PACE · 17 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED