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.The key idea for solving Range Sum Query 2D - Immutable efficiently is to avoid recalculating sums for every query. A brute-force approach would sum elements inside the given rectangle each time, leading to slow performance when many queries are made.
A better approach is to precompute a 2D prefix sum matrix. In this matrix, each cell stores the cumulative sum of elements from the top-left corner to that position. This preprocessing step allows any submatrix sum to be calculated using an inclusion–exclusion formula such as sum(r1,r2,c1,c2) = prefix[r2][c2] - prefix[r1-1][c2] - prefix[r2][c1-1] + prefix[r1-1][c1-1].
After the prefix matrix is built, each query can be answered in constant time. This design-based strategy is ideal when the matrix is immutable and multiple queries are expected.
The preprocessing takes O(m × n) time and space, while each query runs in O(1) time.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| 2D Prefix Sum (Preprocessing + Query) | Preprocessing: O(m × n), Query: O(1) | O(m × n) |
NeetCode
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:
Time Complexity: O(m * n) for construction, O(1) for each query.
Space Complexity: O(m * n) for the prefix sum storage.
1#include <vector>
2using namespace std;
3
4class NumMatrix {
5public:
6 vector<vector<int>> sum;
7 NumMatrix(vector<vector<int>>& matrix) {
8 int m = matrix.size();
9 int n = matrix[0].size();
10 sum.assign(m + 1, vector<int>(n + 1, 0));
11 for (int i = 1; i <= m; ++i) {
12 for (int j = 1; j <= n; ++j) {
sum[i][j] = matrix[i - 1][j - 1] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
}
}
}
int sumRegion(int row1, int col1, int row2, int col2) {
return sum[row2 + 1][col2 + 1] - sum[row2 + 1][col1] - sum[row1][col2 + 1] + sum[row1][col1];
}
};Here, the C++ solution uses nested vectors to create a 2D prefix sum matrix. The sumRegion function utilizes this preprocessed data for efficient calculations.
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.
Time Complexity: O(log m * log n) per update or query.
Space Complexity: O(m * n) for the tree structure.
1#include <vector>
2using namespace std;
3
4class NumMatrix {
5public:
int m, n;
vector<vector<int>> tree;
vector<vector<int>> nums;
NumMatrix(vector<vector<int>>& matrix) {
m = matrix.size();
n = matrix[0].size();
tree.resize(m + 1, vector<int>(n + 1));
nums.resize(m, vector<int>(n));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
update(i, j, matrix[i][j]);
}
}
}
void update(int row, int col, int val) {
int diff = val - nums[row][col];
nums[row][col] = val;
for (int i = row + 1; i <= m; i += i & -i) {
for (int j = col + 1; j <= n; j += j & -j) {
tree[i][j] += diff;
}
}
}
int sumRange(int row1, int col1, int row2, int col2) {
return sum(row2, col2) - sum(row2, col1 - 1) - sum(row1 - 1, col2) + sum(row1 - 1, col1 - 1);
}
private:
int sum(int row, int col) {
int total = 0;
for (int i = row + 1; i > 0; i -= i & -i) {
for (int j = col + 1; j > 0; j -= j & -j) {
total += tree[i][j];
}
}
return total;
}
};Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
The matrix is called immutable because its values never change after initialization. Since updates are not required, we can safely preprocess prefix sums once and use them for all future queries.
Yes, prefix sum problems like this frequently appear in technical interviews at major tech companies. They test understanding of preprocessing techniques, matrix manipulation, and time optimization for repeated queries.
A 2D prefix sum array is the most effective data structure for this problem. It stores cumulative sums so that any submatrix sum can be calculated quickly without recomputing values.
The optimal approach is to use a 2D prefix sum matrix. By preprocessing cumulative sums for the grid, each rectangular sum query can be answered in constant time using an inclusion–exclusion formula.
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.