(44). Range Sum Query 2D - Immutable
Given a 2D matrix matrix, find the sum of the elements inside the
rectangle defined by its upper left corner (row1, col1) and lower
right corner (row2, col2).
Example:
Given matrix = [
[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]
]
sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12
Note:
You may assume that the matrix does not change.
There are many calls to sumRegion function.
You may assume that row1 ≤ row2 and col1 ≤ col2.
Formula for sum matrix:
T[0][0] = matrix[0][0];
//populate the first row.
for (int i=0; i<col; i++) {
T[0][i] = T[0][i-1] + matrix[0][i];
}
//populate the first col.
for (int i=0; i<row; i++) {
T[i][0] = T[i-1][0] + matrix[i-1][0];
}
for (int i=0; i<row; i++) {
for (int j=0; j<col; j++) {
T[i][j] = T[i-1][j] + T[i][j-1] + matrix[i][j] - T[i-1][j-1];
}
}
Forumla for sum region:
public int sumRegion(int row1, int col1, int row2, int col2) {
int sum = T[row2][col2];
if (row1 > 0 && col1 > 0) {
sum = sum - T[row2][col1-1] - T[row1-1][col2] + T[row1-1][col1-1];
} else if (row1 == 0 && col1 > 0) {
sum = sum - T[row2][col1-1];
} else if (col1 == 0 && row1 > 0) {
sum = sum - T[row1-1][col2];
}
return sum;
}
| input matrix |
|
|
|
|
|
| indices |
0 |
1 |
2 |
3 |
4 |
| 0 |
3 |
0 |
1 |
4 |
2 |
| 1 |
5 |
6 |
3 |
2 |
1 |
| 2 |
1 |
2 |
0 |
1 |
5 |
| 3 |
4 |
1 |
0 |
1 |
7 |
| 4 |
1 |
0 |
3 |
0 |
5 |
| sum matrix |
|
|
|
|
|
| indices |
0 |
1 |
2 |
3 |
4 |
| 0 |
3 |
3 |
4 |
8 |
10 |
| 1 |
8 |
14 |
18 |
24 |
27 |
| 2 |
9 |
17 |
21 |
28 |
36 |
| 3 |
13 |
22 |
26 |
34 |
49 |
| 4 |
14 |
23 |
30 |
38 |
58 |
Range Query Sum
- Time complexity: O(n^2)
- Space complexity: O(n^2)