304. Range Sum Query 2D – Immutable

304

MediumPrefix Sum and Difference Array2D prefix sum matrix2D precomputed prefix sums

Range Sum Query 2D – Immutable

Design a NumMatrix class initialized once with an m x n integer matrix. sumRegion(row1, col1, row2, col2) must return the sum of all elements inside the rectangle whose top-left corner is (row1, col1) and bottom-right corner is (row2, col2), inclusive. Many queries will be made.

Open official problem prompt ↗

In plain English

Answer any rectangle-sum query on a fixed 2D grid in constant time after a single preprocessing pass.

Picture it like this

Imagine measuring how much rain fell over a rectangular county. If you keep a running total of rainfall from the map's corner to every point, you can find any county's total by combining four corner readings instead of re-summing every cell.

Example

Input: 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)
Output: 8
Why: The 3x3 block rows 2..4 and cols 1..3 sums to 2+0+1+1+0+1+0+3+0 = 8

Constraints

m == matrix.lengthn == matrix[i].length1 <= m, n <= 200-10^4 <= matrix[i][j] <= 10^40 <= row1 <= row2 < m0 <= col1 <= col2 < nAt most 10^4 calls to sumRegion

Pattern lesson

See the pattern, then code

2D precomputed prefix sums

↗

Prefix Sum and Difference Array

Repeated range queries, subarray totals, balanced counts, or batched range updates.. Let pre[i][j] be the sum of the sub-rectangle from the origin to (i-1, j-1). Any rectangle sum is then found by inclusion-exclusion: take the big block, subtract the strip above and the strip to the left, then add back the top-left corner that was subtracted twice.

New words, made simpleKnow these before the algorithm

2D prefix sum: pre[i][j] holds the sum of every cell in the rectangle from (0,0) to (i-1,j-1).
Inclusion-exclusion: A counting trick: add and subtract overlapping regions so each cell is counted exactly once.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Sum every cell per query

With 10^4 queries on a 200x200 grid this is up to 4*10^8 cell reads; far too slow.

For each query, loop over all rows and columns in the rectangle.

Time O(m*n) per querySpace O(1)

Best choice2D prefix table

Constant-time queries after one pass, exactly what the immutable design rewards.

Precompute cumulative rectangle sums, then combine four table lookups per query.

Time O(m*n) build, O(1) querySpace O(m*n)

The rule we keep true

Invariant

pre[i][j] always equals the sum of the sub-rectangle from the origin to (i-1, j-1), so the four-term formula isolates any target rectangle.

Why this is correct

Reasoning

Subtracting the top strip and the left strip removes everything outside the target rectangle, but the top-left overlap is removed twice, so adding pre[row1][col1] back restores it, leaving exactly the target cells.

The algorithm in three movesSay these aloud before coding

1Build pre sized (m+1) x (n+1) filled with zeros

pre[5][4] - pre[2][4]

2Fill pre[i+1][j+1] = pre[i][j+1] + pre[i+1][j] - pre[i][j] + matrix[i][j]

- pre[5][1] + pre[2][1]

3For a query, return pre[r2+1][c2+1] - pre[r1][c2+1] - pre[r2+1][c1] + pre[r1][c1]

= 8

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

big0

-top1

-left2

+corner3

1 · Readmatrix cell (0,0)=3

2 · AskWhat is pre[1][1]?

3 · Update statepre[1][1] = 0+0-0+3 = 3

4 · ResultBase of the table set

Key takeaway

Inclusion-exclusion: whole block minus top strip minus left strip plus the double-subtracted corner.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 2-13Build the 2D prefix table
Each cell folds in the block above, the block to the left, removes the doubly counted overlap, and adds the raw value.
2
Lines 15-22Four-corner query
One big rectangle minus two strips plus the corner gives the region sum with four O(1) lookups.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

A 1x1 query where row1==row2 and col1==col2 returns a single cell
Querying the full grid returns pre[m][n]
Rectangles touching the top or left edge rely on the zero border row and column

Common beginner mistakes

Forgetting to add pre[row1][col1] back, which double-subtracts the corner
Index confusion between matrix coordinates and the +1-shifted prefix table
Assuming square matrices; m and n can differ

Check your understanding

Why is pre[row1][col1] added back rather than subtracted?

PyPython 3 · solution.py

Optimal

1class NumMatrix:2    def __init__(self, matrix: list[list[int]]):3        m, n = len(matrix), len(matrix[0])4        self.pre = [[0] * (n + 1) for _ in range(m + 1)]5        for i in range(m):6            for j in range(n):7                self.pre[i + 1][j + 1] = (8                    self.pre[i][j + 1]9                    + self.pre[i + 1][j]10                    - self.pre[i][j]11                    + matrix[i][j]12                )1314    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:15        p = self.pre16        return (17            p[row2 + 1][col2 + 1]18            - p[row1][col2 + 1]19            - p[row2 + 1][col1]20            + p[row1][col1]21        )

Time complexityO(m*n) to build, O(1) per queryOptimized

Space complexityO(m*n)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

AmazonGoogleMicrosoft

Range Sum Query 2D – Immutable

Range Sum Query 2D – Immutable

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Prefix Sum and Difference Array