Range Sum Query 2D - Immutable (LeetCode 304)

The problem

You are given a matrix of integers that never changes. Build a class that answers many queries sumRegion(r1, c1, r2, c2): the sum of every cell in the rectangle with top-left corner (r1, c1) and bottom-right corner (r2, c2), inclusive.

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) -> 8

Rows 2 to 4, columns 1 to 3 are 2 0 1 / 1 0 1 / 0 3 0, which add up to 8.

How to think about it

Start with brute force. Loop over every cell in the rectangle per query: O(R·C) each. Slightly better, keep a 1-D prefix sum per row and add R row-ranges per query: O(R) each. With 10⁴ queries both are wasteful.

The key insight: extend prefix sums to two dimensions. Let pre[r][c] be the sum of the rectangle from the origin (0, 0) up to, but not including, row r and column c. Any rectangle is then the big origin rectangle, minus the strip above, minus the strip to the left, plus the top-left corner you subtracted twice. That is inclusion–exclusion, and it is four lookups: O(1).

Building it uses the same idea in reverse. pre[r+1][c+1] = the cell itself + the block above + the block to the left − the overlap of those two (counted twice). One pass over the matrix fills the table. The extra row and column of zeros, as in 1-D, remove all the boundary special cases.

Which pattern is this? Prefix sums, 2-D version. The tell is “many rectangle-sum queries on a fixed grid”.

Approach

1. Create pre of size (R+1) × (C+1), all zeros.
2. For each cell, set pre[r+1][c+1] = m[r][c] + pre[r][c+1] + pre[r+1][c] - pre[r][c].
3. For a query, return pre[r2+1][c2+1] - pre[r1][c2+1] - pre[r2+1][c1] + pre[r1][c1].

Solution

class NumMatrix:
    def __init__(self, m):
        R, C = len(m), len(m[0])
        self.pre = [[0]*(C+1) for _ in range(R+1)]   # padded with a zero row and column
        for r in range(R):
            for c in range(C):
                # cell + block above + block left - overlap counted twice
                self.pre[r+1][c+1] = m[r][c] + self.pre[r][c+1] + self.pre[r+1][c] - self.pre[r][c]
    def sumRegion(self, r1, c1, r2, c2):
        p = self.pre
        # whole - strip above - strip left + corner subtracted twice
        return p[r2+1][c2+1] - p[r1][c2+1] - p[r2+1][c1] + p[r1][c1]
# nm = NumMatrix([[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]])
# nm.sumRegion(2,1,4,3) -> 8

Dry run

The built table pre (row 0 and column 0 are the zero padding):

For sumRegion(2, 1, 4, 3):

38 − 24 − 14 + 8 = 8.

Complexity

• Time: O(R·C) to build, O(1) per query. Each cell is computed once from three neighbours; a query is four lookups.
• Space: O(R·C). The padded table has (R+1)(C+1) entries.

Edge cases and pitfalls

• Forgetting to add the corner back gives an answer that is too small by p[r1][c1].
• Index shift: pre is offset by one, so the query uses r2+1 and c2+1 for the far corner but plain r1 and c1 for the near edges.
• Single-cell query (r1 == r2, c1 == c2) returns just that cell’s value.
• Empty matrix: m[0] would fail. The constraints say the matrix is at least 1×1; guard it if they do not.
• Mutable matrix (LeetCode 308) breaks this; it needs a 2-D Fenwick tree.

Related problems

• Range Sum Query - Immutable (LeetCode 303): the 1-D version of the same idea.
• Minimum Path Sum (LeetCode 64): another grid table filled from the cell above and the cell to the left.
• Subarray Sum Equals K (LeetCode 560): prefix sums combined with a hash map for counting.