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.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.
C++
Java
Python
C#
JavaScript
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.
Java
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. |
Range Sum Query 2D - Immutable - Leetcode 304 - Python • NeetCode • 50,535 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