LeetCode 304 - Range Sum Query 2D - Immutable

The problem asks us to design a data structure that can efficiently answer multiple rectangular sum queries on a fixed 2D matrix.

leetcodemediumarraydesignmatrixprefix-sum

LeetCode Problem 304

Difficulty: 🟡 Medium
Topics: Array, Design, Matrix, Prefix Sum

Solution

Problem Understanding

The problem asks us to design a data structure that can efficiently answer multiple rectangular sum queries on a fixed 2D matrix.

We are given a matrix of integers, and each query specifies four coordinates:

  • (row1, col1) represents the top-left corner of a rectangle
  • (row2, col2) represents the bottom-right corner of the rectangle

For every query, we must return the sum of all elements inside that rectangle, inclusive of both boundaries.

The important detail is that the matrix never changes after initialization. This makes the problem "immutable", meaning we only need to preprocess the matrix once and then support fast read-only queries afterward.

A naive solution would recompute the rectangle sum every time by iterating over all cells in the requested region. That works functionally, but it becomes inefficient when many queries are performed. The problem explicitly requires that sumRegion run in O(1) time, which strongly suggests preprocessing.

The constraints help clarify the intended solution:

  • m, n <= 200, so the matrix is not extremely large
  • Up to 10^4 calls to sumRegion can occur
  • Matrix values can be negative, so we cannot rely on monotonic properties or pruning
  • The matrix is guaranteed to contain at least one element

The large number of queries compared to the relatively small matrix size tells us that preprocessing is worthwhile. Spending O(m * n) time during construction is acceptable if it allows constant-time queries afterward.

Several edge cases are important:

  • Queries may ask for a single cell
  • Queries may span the entire matrix
  • Queries may start at row 0 or column 0
  • Matrix values may be negative
  • Rectangles may include only one row or one column

The biggest implementation challenge is correctly handling boundaries without producing off-by-one errors.

Approaches

Brute Force Approach

The most straightforward solution is to compute the sum directly for every query.

For each sumRegion(row1, col1, row2, col2) call, we iterate through every row from row1 to row2, and every column from col1 to col2, adding all values together.

This approach is correct because it explicitly visits every element inside the requested rectangle exactly once.

However, this becomes inefficient when many queries are performed. In the worst case, a query may cover the entire matrix, requiring O(m * n) work per query. Since up to 10^4 queries are allowed, the total runtime could become extremely large.

Optimal Approach, 2D Prefix Sum

The key observation is that the matrix never changes. Because of this, we can preprocess cumulative sums once and reuse them for every query.

We construct a 2D prefix sum matrix where each cell stores the sum of all elements from the top-left corner (0,0) to the current position.

Using this structure, any rectangular sum can be computed using inclusion-exclusion:

  • Start with the sum of the large rectangle from (0,0) to (row2,col2)
  • Subtract the area above the target rectangle
  • Subtract the area to the left of the target rectangle
  • Add back the overlapping area that was subtracted twice

This transforms each query into a constant number of arithmetic operations.

Approach Time Complexity Space Complexity Notes
Brute Force O(m * n) per query O(1) Iterates through every cell in the rectangle
Optimal O(1) per query after preprocessing O(m * n) Uses a 2D prefix sum matrix

Algorithm Walkthrough

Step 1: Create a Prefix Sum Matrix

We build a new matrix called prefix with dimensions (rows + 1) x (cols + 1).

The extra row and column simplify boundary handling. Instead of constantly checking whether indices go negative, we can safely use index arithmetic.

Each prefix[r][c] stores the sum of all values in the rectangle from (0,0) to (r-1,c-1) in the original matrix.

Step 2: Fill the Prefix Sum Matrix

For every cell in the original matrix, compute:

$prefix[r][c]=matrix[r-1][c-1]+prefix[r-1][c]+prefix[r][c-1]-prefix[r-1][c-1]$

This formula works because:

  • prefix[r-1][c] contains the sum above
  • prefix[r][c-1] contains the sum to the left
  • The overlap prefix[r-1][c-1] gets counted twice, so we subtract it once
  • Finally, add the current matrix value

Step 3: Answer Queries Using Inclusion-Exclusion

To compute the sum of a rectangle:

  • Start with the full area from (0,0) to (row2,col2)
  • Remove rows above the target rectangle
  • Remove columns left of the target rectangle
  • Add back the overlap

The query formula becomes:

$sum=prefix[row2+1][col2+1]-prefix[row1][col2+1]-prefix[row2+1][col1]+prefix[row1][col1]$

Each query now takes constant time because it only uses four table lookups.

Why it works

The prefix matrix maintains the invariant that each entry contains the sum of all elements from the origin to that position.

Because rectangular regions can be represented as combinations of overlapping larger rectangles, inclusion-exclusion guarantees that every element inside the target rectangle is counted exactly once, while all outside elements cancel out.

Python Solution

from typing import List

class NumMatrix:

    def __init__(self, matrix: List[List[int]]):
        rows = len(matrix)
        cols = len(matrix[0])

        # Extra row and column for easier boundary handling
        self.prefix = [[0] * (cols + 1) for _ in range(rows + 1)]

        for r in range(1, rows + 1):
            for c in range(1, cols + 1):
                self.prefix[r][c] = (
                    matrix[r - 1][c - 1]
                    + self.prefix[r - 1][c]
                    + self.prefix[r][c - 1]
                    - self.prefix[r - 1][c - 1]
                )

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        return (
            self.prefix[row2 + 1][col2 + 1]
            - self.prefix[row1][col2 + 1]
            - self.prefix[row2 + 1][col1]
            + self.prefix[row1][col1]
        )

# Your NumMatrix object will be instantiated and called as such:
# obj = NumMatrix(matrix)
# param_1 = obj.sumRegion(row1, col1, row2, col2)

The implementation begins by constructing a 2D prefix sum matrix during initialization.

An extra row and column are added so that every rectangle calculation remains uniform, even when the query touches the top or left border. Without this padding, the implementation would require multiple conditional checks.

The nested loops compute cumulative sums incrementally. Each cell combines:

  • the current matrix value,
  • the cumulative sum above,
  • the cumulative sum to the left,
  • minus the overlapping region counted twice.

The sumRegion method then applies the inclusion-exclusion formula directly. Since all preprocessing is already complete, the query requires only four array accesses and three arithmetic operations.

Go Solution

type NumMatrix struct {
	prefix [][]int
}

func Constructor(matrix [][]int) NumMatrix {
	rows := len(matrix)
	cols := len(matrix[0])

	prefix := make([][]int, rows+1)

	for i := range prefix {
		prefix[i] = make([]int, cols+1)
	}

	for r := 1; r <= rows; r++ {
		for c := 1; c <= cols; c++ {
			prefix[r][c] =
				matrix[r-1][c-1] +
					prefix[r-1][c] +
					prefix[r][c-1] -
					prefix[r-1][c-1]
		}
	}

	return NumMatrix{
		prefix: prefix,
	}
}

func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
	return this.prefix[row2+1][col2+1] -
		this.prefix[row1][col2+1] -
		this.prefix[row2+1][col1] +
		this.prefix[row1][col1]
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * obj := Constructor(matrix);
 * param_1 := obj.SumRegion(row1,col1,row2,col2);
 */

The Go implementation mirrors the Python solution closely.

Slices are used instead of arrays because matrix dimensions are determined at runtime. Go initializes integer slices to zero automatically, which makes constructing the padded prefix matrix straightforward.

The problem constraints guarantee that integer overflow is not an issue for standard Go int values.

Worked Examples

Consider the 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

Building the Prefix Matrix

The prefix matrix becomes:
0 0 0 0 0 0
0 3 3 4 8 10
0 8 14 18 24 27
0 9 17 21 28 36
0 13 22 26 34 49
0 14 23 30 38 58

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

Target rectangle:

2 0 1
1 0 1
0 3 0

Sum should equal 8.

Using the formula:

prefix[5][4] = 38
prefix[2][4] = 24
prefix[5][1] = 14
prefix[2][1] = 8

Calculation:

38 - 24 - 14 + 8 = 8

Query 2: sumRegion(1, 1, 2, 2)

Target rectangle:

6 3
2 0

Using the formula:

prefix[3][3] = 21
prefix[1][3] = 4
prefix[3][1] = 9
prefix[1][1] = 3

Calculation:

21 - 4 - 9 + 3 = 11

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

Target rectangle:

3 2 1
0 1 5

Using the formula:

prefix[3][5] = 36
prefix[1][5] = 10
prefix[3][2] = 17
prefix[1][2] = 3

Calculation:

36 - 10 - 17 + 3 = 12

Complexity Analysis

Measure Complexity Explanation
Time O(m * n) preprocessing, O(1) per query Prefix matrix built once, queries use constant arithmetic
Space O(m * n) Stores the prefix sum matrix

The preprocessing step visits every matrix cell exactly once, so initialization requires O(m * n) time.

Each query performs a constant number of operations regardless of rectangle size, giving O(1) query complexity.

The additional prefix matrix stores one cumulative value per matrix cell plus padding, resulting in O(m * n) extra space.

Test Cases

from typing import List

class NumMatrix:

    def __init__(self, matrix: List[List[int]]):
        rows = len(matrix)
        cols = len(matrix[0])

        self.prefix = [[0] * (cols + 1) for _ in range(rows + 1)]

        for r in range(1, rows + 1):
            for c in range(1, cols + 1):
                self.prefix[r][c] = (
                    matrix[r - 1][c - 1]
                    + self.prefix[r - 1][c]
                    + self.prefix[r][c - 1]
                    - self.prefix[r - 1][c - 1]
                )

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        return (
            self.prefix[row2 + 1][col2 + 1]
            - self.prefix[row1][col2 + 1]
            - self.prefix[row2 + 1][col1]
            + self.prefix[row1][col1]
        )

# Example from problem statement
matrix = 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]
])

assert matrix.sumRegion(2, 1, 4, 3) == 8  # standard rectangle
assert matrix.sumRegion(1, 1, 2, 2) == 11  # centered rectangle
assert matrix.sumRegion(1, 2, 2, 4) == 12  # rectangle touching right edge

# Single cell matrix
matrix = NumMatrix([[5]])
assert matrix.sumRegion(0, 0, 0, 0) == 5  # minimal input

# Entire matrix query
matrix = NumMatrix([
    [1, 2],
    [3, 4]
])
assert matrix.sumRegion(0, 0, 1, 1) == 10  # full matrix sum

# Single row query
matrix = NumMatrix([
    [1, 2, 3, 4]
])
assert matrix.sumRegion(0, 1, 0, 3) == 9  # one-dimensional horizontal range

# Single column query
matrix = NumMatrix([
    [1],
    [2],
    [3]
])
assert matrix.sumRegion(1, 0, 2, 0) == 5  # one-dimensional vertical range

# Negative values
matrix = NumMatrix([
    [-1, -2],
    [-3, -4]
])
assert matrix.sumRegion(0, 0, 1, 1) == -10  # negative totals

# Mixed positive and negative
matrix = NumMatrix([
    [1, -1],
    [-1, 1]
])
assert matrix.sumRegion(0, 0, 1, 1) == 0  # cancellation case

# Query touching top border
matrix = NumMatrix([
    [1, 2],
    [3, 4]
])
assert matrix.sumRegion(0, 0, 0, 1) == 3  # top row

# Query touching left border
assert matrix.sumRegion(0, 0, 1, 0) == 4  # left column
Test Why
Standard example queries Verifies correctness against official examples
Single cell matrix Validates smallest possible input
Entire matrix query Ensures full-range calculations work
Single row query Tests horizontal boundary handling
Single column query Tests vertical boundary handling
Negative values Ensures sums work with negatives
Mixed positive and negative Tests cancellation behavior
Top border query Validates zero-index row handling
Left border query Validates zero-index column handling

Edge Cases

Queries Touching the Top or Left Border

Rectangles that begin at row 0 or column 0 are a common source of off-by-one errors.

Without careful handling, subtraction formulas may attempt to access negative indices. The implementation avoids this entirely by using a padded prefix matrix with one extra row and column initialized to zero.

This allows every query to use the same formula uniformly, regardless of whether the rectangle touches a border.

Single Cell Queries

A rectangle may contain exactly one element.

This is important because some implementations accidentally treat ranges as exclusive rather than inclusive. The prefix sum formula works correctly even when row1 == row2 and col1 == col2, because the inclusion-exclusion arithmetic still isolates exactly one value.

Negative Numbers

The matrix can contain negative integers.

Some optimization strategies rely on monotonic sums or assumptions that values are non-negative, but those approaches would fail here. Prefix sums work regardless of sign because they are purely arithmetic accumulations.

The implementation correctly handles negative totals, mixed values, and cancellation effects without requiring any special logic.