Generated by Codex with GPT-5

Quick facts

Problem gist

The class receives a fixed 2D matrix and must answer many rectangle-sum queries. Each query gives the top-left cell (row1, col1) and the bottom-right cell (row2, col2), and asks for the sum of every matrix value inside that inclusive rectangle.

The word “immutable” is the key constraint. The matrix never changes after construction, so the expensive work can be done once in the constructor. After that, every query should be answered in O(1) time.

A direct scan is easy but too slow when there are many queries. If a rectangle covers most of the matrix, scanning it costs O(m * n) per call. Even row-by-row prefix sums only reduce a query to O(number of rows in the rectangle). The optimal solution precomputes enough information to answer any rectangle with four table lookups.

Deriving the optimal solution

Start with the one-dimensional version. If prefix[i] stores the sum of everything before index i, then the sum from left through right is:

prefix[right + 1] - prefix[left]

The two-dimensional version uses the same idea, but each prefix cell stores the sum of a rectangle from the matrix origin to that point. Define prefix[row][col] as the sum of all original cells with row index < row and column index < col. The extra leading row and column of zeroes make the indexing cleaner.

To build prefix, each cell combines the region above it, the region to its left, subtracts the overlap counted twice, and adds the current matrix value:

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

To answer a query, think of the desired rectangle as a large prefix rectangle with two unwanted strips removed:

Take the sum from the origin to the rectangle’s bottom-right corner.

Subtract the area above the rectangle.

Subtract the area left of the rectangle.

Add back the top-left overlap, because it was subtracted twice.

That inclusion-exclusion formula gives constant-time queries.

Python solution

from typing import List


class NumMatrix:
    def __init__(self, matrix: List[List[int]]):
        self._prefix_sum = self._build_prefix_sum(matrix)

    @staticmethod
    def _build_prefix_sum(matrix: List[List[int]]) -> List[List[int]]:
        if not matrix or not matrix[0]:
            return [[0]]

        row_count = len(matrix)
        column_count = len(matrix[0])
        prefix_sum = [[0] * (column_count + 1) for _ in range(row_count + 1)]

        for row_index in range(1, row_count + 1):
            for column_index in range(1, column_count + 1):
                current_value = matrix[row_index - 1][column_index - 1]
                prefix_sum[row_index][column_index] = (
                    current_value
                    + prefix_sum[row_index - 1][column_index]
                    + prefix_sum[row_index][column_index - 1]
                    - prefix_sum[row_index - 1][column_index - 1]
                )

        return prefix_sum

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        top = row1
        left = col1
        bottom = row2 + 1
        right = col2 + 1

        prefix_sum = self._prefix_sum

        return (
            prefix_sum[bottom][right]
            - prefix_sum[top][right]
            - prefix_sum[bottom][left]
            + prefix_sum[top][left]
        )


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

Complexity

The constructor visits each cell once, so preprocessing takes O(m * n) time for an m by n matrix.

Each sumRegion call does four prefix lookups and constant arithmetic, so query time is O(1).

The prefix table stores one extra row and one extra column, so extra space is O(m * n).

Interview follow-ups

What if the matrix can be updated?

The plain 2D prefix table is excellent for immutable data but weak for updates. If one matrix cell changes, every prefix cell down and to the right may need to change, so a single update can cost O(m * n).

For frequent point updates and rectangle-sum queries, the usual upgrade is a 2D Binary Indexed Tree, also called a 2D Fenwick tree. It stores partial sums in a structure where both update(row, col, delta) and prefix-sum lookup take O(log m * log n) time. A rectangle sum is still computed by inclusion-exclusion over four prefix queries.

This trades constant-time immutable queries for balanced dynamic operations. The implementation is more complex, but it is the right direction when updates are part of the API.

What if preprocessing memory is too expensive?

The optimal immutable query time requires storing a full 2D prefix table, which costs O(m * n) extra memory. If memory is the limiting factor, the interviewer may accept a slower query in exchange for less storage.

One compromise is row-wise prefix sums. Store a prefix sum for each row, then answer a rectangle by summing the requested column range for every row in the rectangle. That keeps the same O(m * n) asymptotic storage as a 2D prefix table, but it can be easier to adapt and may have lower overhead in some languages. The query time becomes O(row2 - row1 + 1).

If memory must be much smaller than the input size, then the algorithm cannot guarantee O(1) arbitrary rectangle queries in general. It must either scan part of the matrix at query time or rely on extra assumptions, such as sparse nonzero values or a restricted query pattern.

What if the matrix is sparse?

If most values are zero and the matrix is very large, a dense prefix table may waste space. A practical sparse approach is to store only nonzero cells, often grouped by row or by a coordinate index, then sum only relevant nonzero values inside the rectangle.

For example, each row can keep sorted (column, value) pairs plus a row-local prefix over those nonzero entries. A query then checks only rows in the rectangle and binary-searches the requested column range within each row. This can be efficient when rectangles are short or the data is extremely sparse.

The tradeoff is that the worst-case query is no longer O(1). Sparse representations optimize real memory usage and common sparse workloads, while the dense 2D prefix table optimizes worst-case query speed.

What if the query asks for the average value in a rectangle?

The same prefix-sum table still works. First compute the rectangle sum in O(1), then divide by the number of cells in the rectangle:

(row2 - row1 + 1) * (col2 - col1 + 1)

This works because average is derived from sum and count. The count is known directly from the coordinates, so no additional data structure is required. The preprocessing, query time, and space complexity stay the same.

What if values can be negative?

Negative values do not change the algorithm. Prefix sums rely on addition and subtraction, not ordering or positivity. Inclusion-exclusion still works because it is only accounting for which areas are included, removed, and added back.

The main practical concern is integer range. Python integers grow as needed, so overflow is not an issue. In fixed-width languages, use a type large enough for the maximum possible rectangle sum. With larger constraints, long or long long may be necessary even when each individual matrix value fits in int.