#304 Range Sum Query 2D - Immutable
the problem
In plain words
Design a class built from a matrix that answers many sumRegion(row1, col1, row2, col2) queries: the sum inside that rectangle, inclusive. Each query must be O(1).
in matrix = [[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]; sumRegion(2,1,4,3), sumRegion(1,1,2,2), sumRegion(1,2,2,4)
out 8, 11, 12
- 1 ≤ rows, cols ≤ 200
- -10⁴ ≤ matrix[i][j] ≤ 10⁴
- Up to 10⁴ queries
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
Design: implement every operation. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternPrefix sums
Store the sum of every top-left rectangle. Any rectangle = whole − strip above − strip left + the corner you subtracted twice.
solutions
From brute force to optimal
Loop over the rectangle each time.
- For r in row1..row2, c in col1..col2: sum += matrix[r][c].
A query can cover the whole matrix.
Just the matrix reference.
/** LeetCode names this class NumMatrix. */class NumMatrixLoop { private final int[][] matrix; public NumMatrixLoop(int[][] matrix) { this.matrix = matrix; } public int sumRegion(int row1, int col1, int row2, int col2) { int sum = 0; for (int r = row1; r <= row2; r++) for (int c = col1; c <= col2; c++) sum += matrix[r][c]; // every cell, every call return sum; }}1D prefix sums on each row; a query sums one O(1) difference per row.
- rowPrefix[r][c+1] = rowPrefix[r][c] + matrix[r][c].
- Query: add rowPrefix[r][col2+1] − rowPrefix[r][col1] for each row.
One subtraction per row in the range.
A prefix row per matrix row.
class NumMatrixRows { private final int[][] rowPrefix; // rowPrefix[r][c] = sum of matrix[r][0..c-1] public NumMatrixRows(int[][] matrix) { int rows = matrix.length, cols = matrix[0].length; rowPrefix = new int[rows][cols + 1]; for (int r = 0; r < rows; r++) for (int c = 0; c < cols; c++) rowPrefix[r][c + 1] = rowPrefix[r][c] + matrix[r][c]; } public int sumRegion(int row1, int col1, int row2, int col2) { int sum = 0; for (int r = row1; r <= row2; r++) sum += rowPrefix[r][col2 + 1] - rowPrefix[r][col1]; // O(1) per row return sum; }}p[r+1][c+1] = cell + up + left − up-left; query with four lookups.
- Build p with an extra zero row and column.
- Query: p[r2+1][c2+1] − p[r1][c2+1] − p[r2+1][c1] + p[r1][c1].
Each cell is built once; four lookups per query.
(r + 1) × (c + 1) table.
class NumMatrix { private final int[][] p; // p[r][c] = sum of the rectangle (0,0)..(r-1,c-1) public NumMatrix(int[][] matrix) { int rows = matrix.length, cols = matrix[0].length; p = new int[rows + 1][cols + 1]; for (int r = 0; r < rows; r++) for (int c = 0; c < cols; c++) p[r + 1][c + 1] = matrix[r][c] + p[r][c + 1] + p[r + 1][c] - p[r][c]; } public int sumRegion(int row1, int col1, int row2, int col2) { // whole - strip above - strip left + the corner that was subtracted twice return p[row2 + 1][col2 + 1] - p[row1][col2 + 1] - p[row2 + 1][col1] + p[row1][col1]; }}Build and query
in the room
How to say it in the interview
talk track
- Draw the four rectangles and shade the doubly-subtracted corner. It makes the formula obvious.
- Use the +1 offset to avoid bounds checks.
traps
- Off-by-one between matrix coordinates and the shifted p coordinates.
- Forgetting to add the corner back.
what they ask next
Follow-ups
With updates (LC 308)?
A 2D Fenwick tree gives O(log r · log c) per update and query.
before you submit
Edge cases to test
- A 1×1 query.
- The whole matrix as one query.
- Rectangles touching row 0 or column 0 — the zero border handles them.
practise next
Similar problems
- #303Range Sum Query - ImmutableEasyin Hashing
- #307Range Sum Query - MutableMediumin Range Queries & Strings