Given a 2D matrix matrix, handle multiple queries of the following type:
matrix inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).Implement the NumMatrix class:
NumMatrix(int[][] matrix) Initializes the object with the integer matrix matrix.int sumRegion(int row1, int col1, int row2, int col2) Returns the sum of the elements of matrix inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).You must design an algorithm where sumRegion works on O(1) time complexity.
Example 1:
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.lengthn == matrix[i].length1 <= m, n <= 200-104 <= matrix[i][j] <= 1040 <= row1 <= row2 < m0 <= col1 <= col2 < n104 calls will be made to sumRegion.Problem Overview: You receive a 2D matrix and must repeatedly return the sum of elements inside a rectangular region defined by (row1, col1) and (row2, col2). The matrix never changes, but the number of queries can be large. A naive sum per query is too slow, so the goal is to preprocess the matrix so each query runs in constant time.
Approach 1: Using 2D Prefix Sum (Preprocessing O(m*n), Query O(1))
This approach builds a cumulative sum matrix where each cell stores the total of all elements from the top-left corner to that position. During preprocessing, iterate through the matrix and compute prefix[i][j] using values from the top, left, and top-left diagonal. Once built, any submatrix sum can be computed using the inclusion–exclusion principle: subtract the extra regions above and left, then add back the overlapping corner. Query computation becomes a few constant-time arithmetic operations. Time complexity is O(m*n) to build the prefix matrix and O(1) per query, with O(m*n) extra space. This technique is a standard extension of prefix sum applied to a matrix and works well when the matrix is immutable and queries are frequent.
Approach 2: 2D Fenwick Tree (Binary Indexed Tree) (Update O(log m * log n), Query O(log m * log n))
A 2D Fenwick Tree stores partial sums in a structured tree-like array that supports efficient region queries. Each update propagates through index ranges using bit manipulation, and prefix sums are computed by traversing parent nodes. A rectangular sum query is derived by combining four prefix queries, similar to the prefix-sum inclusion–exclusion formula. Query and update operations both run in O(log m * log n) time with O(m*n) space. Even though the original problem is immutable, this structure becomes valuable if the matrix supports updates. It relies on concepts from array indexing and tree-based cumulative structures.
Recommended for interviews: The expected solution is the 2D Prefix Sum approach. Interviewers want to see that you recognize repeated range queries and convert them into a preprocessing problem. Building the prefix matrix shows understanding of cumulative sums and inclusion–exclusion logic. Mentioning a 2D Fenwick Tree demonstrates deeper knowledge of data structures for mutable range queries, but implementing it is usually unnecessary unless updates are part of the problem.
This approach involves preprocessing the matrix to build a prefix sum array. The prefix sum at any index (i, j) in this array contains the sum of elements from (0, 0) to (i, j). With this preprocessed information, calculating any submatrix sum becomes feasible in constant time using the inclusion-exclusion principle.
For a query with corners (row1, col1) and (row2, col2), compute the sum using:
In the C implementation, a 2D prefix sum array is created during initialization. The sum is calculated by adding and subtracting precomputed values from this 2D array.
Time Complexity: O(m * n) for construction, O(1) for each query.
Space Complexity: O(m * n) for the prefix sum storage.
This approach involves using a 2D Fenwick Tree to update and query the matrix sums efficiently. Fenwick Trees provide a structure that allows for querying prefix sums, updating values, and hence facilitating the calculation of region sums after updates.
This C++ solution makes use of a 2D Fenwick Tree which is efficient for both point updates and querying prefix sums, making it feasible to handle dynamic updation scenarios.
Time Complexity: O(log m * log n) per update or query.
Space Complexity: O(m * n) for the tree structure.
| Approach | Complexity |
|---|---|
| Approach 1: Using 2D Prefix Sum | Time Complexity: O(m * n) for construction, O(1) for each query. |
| Approach 2: Using Fenwick Tree (Binary Indexed Tree) 2D | Time Complexity: O(log m * log n) per update or query. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| 2D Prefix Sum | Preprocess: O(m*n) Query: O(1) | O(m*n) | Best choice when the matrix is immutable and many range sum queries are expected |
| 2D Fenwick Tree (Binary Indexed Tree) | Update: O(log m * log n) Query: O(log m * log n) | O(m*n) | Useful when the matrix can change and you still need fast region sum queries |
Range Sum Query 2D - Immutable - Leetcode 304 - Python • NeetCode • 75,087 views views
Watch 9 more video solutions →Practice Range Sum Query 2D - Immutable with our built-in code editor and test cases.
Practice on FleetCode