#304

Medium

LeetCode Problem Workspace

Range Sum Query 2D - Immutable

Design a 2D matrix class that efficiently handles sum queries with O(1) time complexity using a prefix sum approach.

Problem Statement

You are given a 2D matrix and need to handle multiple sum queries where each query asks for the sum of elements in a rectangular submatrix. You must design a solution where each query can be answered in constant time, O(1).

To achieve this, implement the NumMatrix class, which will efficiently calculate the sum of elements in any submatrix, utilizing a precomputed prefix sum matrix. The sumRegion function should perform in constant time, meaning that the setup of the data structure should handle the complexity of computation for each query.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

Input ["NumMatrix", "sumRegion", "sumRegion", "sumRegion"] [[[[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]]], [2, 1, 4, 3], [1, 1, 2, 2], [1, 2, 2, 4]] Output [null, 8, 11, 12]

Explanation NumMatrix numMatrix = new 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]]); numMatrix.sumRegion(2, 1, 4, 3); // return 8 (i.e sum of the red rectangle) numMatrix.sumRegion(1, 1, 2, 2); // return 11 (i.e sum of the green rectangle) numMatrix.sumRegion(1, 2, 2, 4); // return 12 (i.e sum of the blue rectangle)

Constraints

m == matrix.length
n == matrix[i].length
1 <= m, n <= 200
-104 <= matrix[i][j] <= 104
0 <= row1 <= row2 < m
0 <= col1 <= col2 < n
At most 104 calls will be made to sumRegion.

Solution Approach

Prefix Sum Matrix

Use a prefix sum matrix to precompute the sums of all submatrices in O(m * n) time, where m and n are the dimensions of the matrix. This matrix will store the sum of elements from the top-left corner to any position (i, j). Each sum query can then be answered in constant time by subtracting values from the prefix sum matrix.

Space Optimization

The space complexity of the prefix sum matrix can be optimized to O(m * n), which is acceptable given the constraints. The class should store the prefix sum matrix and compute sums only when necessary, avoiding repeated calculations for each query.

Efficient Query Handling

Each query is processed in O(1) time by leveraging the precomputed sums. Given that the matrix is static and only sum queries are performed, this approach ensures that subsequent queries are extremely fast after the initial setup.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity for constructing the prefix sum matrix is O(m * n), where m is the number of rows and n is the number of columns. Each query is answered in O(1) time, and the space complexity is O(m * n) to store the prefix sum matrix. These complexities meet the problem's constraints effectively.

What Interviewers Usually Probe

Candidates should demonstrate an understanding of prefix sums and how to apply them to a 2D matrix.
Look for familiarity with space and time trade-offs, especially regarding the need to store and update the prefix sum matrix.
Pay attention to how candidates approach the optimization of the query time, ensuring O(1) complexity for sumRegion.

Common Pitfalls or Variants

Common pitfalls

Failing to precompute the prefix sum matrix, leading to inefficient solutions.
Incorrectly handling the boundaries of the matrix when calculating sumRegion, which can result in out-of-bounds errors.
Overcomplicating the solution by not focusing on the O(1) query requirement, instead implementing less efficient methods.

Follow-up variants

Allowing for dynamic updates to the matrix, which would require modifying the prefix sum after each update.
Handling queries for different types of submatrices, such as those that cover rows or columns.
Improving space efficiency by using rolling sums or other data structures for large matrices.

FAQ

What is the optimal way to handle multiple sum queries on a 2D matrix?

The optimal solution is to use a prefix sum matrix, where each query can be answered in constant time, O(1), by using precomputed sums.

How do you avoid recalculating the sum for every query in Range Sum Query 2D - Immutable?

By storing the sum of submatrices in a prefix sum matrix, each query can be answered in constant time without recalculating sums.

What data structure is best suited for the Range Sum Query 2D - Immutable problem?

The best data structure is a 2D prefix sum matrix that stores cumulative sums and allows fast query processing in O(1) time.

How does the space complexity of the prefix sum matrix affect the solution?

The space complexity of the prefix sum matrix is O(m * n), which is manageable within the problem's constraints and necessary for efficient querying.

Can you modify the Range Sum Query 2D - Immutable to handle dynamic updates?

Yes, by modifying the prefix sum matrix after each update, you can handle dynamic updates, but this will increase the complexity of the solution.

terminal

Solution

Solution 1: Two-dimensional Prefix Sum

We use $s[i + 1][j + 1]$ to represent the sum of all elements in the upper left part of the $i$th row and $j$th column, where indices $i$ and $j$ both start from $0$. We can get the following prefix sum formula:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

class NumMatrix:
    def __init__(self, matrix: List[List[int]]):
        m, n = len(matrix), len(matrix[0])
        self.s = [[0] * (n + 1) for _ in range(m + 1)]
        for i, row in enumerate(matrix):
            for j, v in enumerate(row):
                self.s[i + 1][j + 1] = (
                    self.s[i][j + 1] + self.s[i + 1][j] - self.s[i][j] + v
                )

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


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

Continue Practicing

#363 max sum of rectangle no larger than k #731 my calendar ii #1074 number of submatrices that sum to target