This content originally appeared on DEV Community and was authored by seanpgallivan
This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.
Leetcode Problem #304 (Medium): Range Sum Query 2D - Immutable
Description:
(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)
Given a 2D matrix
matrix, handle multiple queries of the following type:
- Calculate the sum of the elements of
matrixinside the rectangle defined by its upper left corner(row1, col1)and lower right corner(row2, col2).Implement the
NumMatrixclass:
NumMatrix(int[][] matrix)Initializes the object with the integer matrixmatrix.int sumRegion(int row1, int col1, int row2, int col2)Returns the sum of the elements ofmatrixinside the rectangle defined by its upper left corner(row1, col1)and lower right corner(row2, col2).
Examples:
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)Visual:
Constraints:
m == matrix.lengthn == matrix[i].length1 <= m, n <= 200-10^5 <= matrix[i][j] <= 10^50 <= row1 <= row2 < m0 <= col1 <= col2 < n- At most
10^4calls will be made tosumRegion.
Idea:
(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)
This problem brings up one of the characteristics of a 2D matrix: the sum of the elements in any rectangular range of a matrix (M) can be defined mathematically by the overlap of four other rectangular ranges that originate at M[0][0].
The sum of the rectangle (0,0)->(i,j) is equal to the cell (i,j), plus the rectangle (0,0)->(i,j-1), plus the rectangle (0,0)->(i-1,j), minus the rectangle (0,0)->(i-1,j-1). We subtract the last rectangle because it represents the overlap of the previous two rectangles that were added.
With this information, we can use a dynamic programming (DP) approach to build a prefix sum matrix (dp) from M iteratively, where dp[i][j] will represent the sum of the rectangle (0,0)->(i,j). We'll add an extra row and column in order to prevent out-of-bounds issues at i-1 and j-1 (similar to a prefix sum array), and we'll fill dp with 0s.
At each cell, we'll add its value from M to the dp values of the cell on the left and the one above, which represent their respective rectangle sums, and then subtract from that the top-left diagonal value, which represents the overlapping rectangle of the previous two additions.
Then, we just reverse the process for sumRegion(): We start with the sum at dp[R2+1][C2+1] (due to the added row/column), then subtract the left and top rectangles before adding back in the doubly-subtracted top-left diagonal rectangle.
(Note: Even though the test cases will pass when using an int matrix for dp, the values of dp can range from -4e9 to 4e9 per the listed constraints, so we should use a data type capable of handling more than 32 bits.)
-
Time Complexity:
- constructor: O(M * N) where M and N are the dimensions of the input matrix
- sumRegion: O(1)
-
Space Complexity:
- constructor: O(M * N) for the DP matrix
- constructor: O(1) if you're able to modify the input and use an in-place DP approach
- sumRegion: O(1)
Javascript Code:
(Jump to: Problem Description || Solution Idea)
class NumMatrix {
constructor(M) {
let ylen = M.length + 1, xlen = M[0].length + 1
this.dp = Array.from({length: ylen}, () => new Array(xlen).fill(0))
for (let i = 1; i < ylen; i++)
for (let j = 1; j < xlen; j++)
this.dp[i][j] = M[i-1][j-1] + this.dp[i-1][j] + this.dp[i][j-1] - this.dp[i-1][j-1]
}
sumRegion(R1, C1, R2, C2) {
return this.dp[R2+1][C2+1] - this.dp[R2+1][C1] - this.dp[R1][C2+1] + this.dp[R1][C1]
}
};
Python Code:
(Jump to: Problem Description || Solution Idea)
class NumMatrix:
def __init__(self, M: List[List[int]]):
ylen, xlen = len(M) + 1, len(M[0]) + 1
self.dp = [[0] * xlen for _ in range(ylen)]
for i in range(ylen):
for j in range(xlen):
self.dp[i][j] = M[i-1][j-1] + self.dp[i-1][j] + self.dp[i][j-1] - self.dp[i-1][j-1]
def sumRegion(self, R1: int, C1: int, R2: int, C2: int) -> int:
return self.dp[R2+1][C2+1] - self.dp[R2+1][C1] - self.dp[R1][C2+1] + self.dp[R1][C1]
Java Code:
(Jump to: Problem Description || Solution Idea)
class NumMatrix {
long[][] dp;
public NumMatrix(int[][] M) {
int ylen = M.length + 1, xlen = M[0].length + 1;
dp = new long[ylen][xlen];
for (int i = 1; i < ylen; i++)
for (int j = 1; j < xlen; j++)
dp[i][j] = M[i-1][j-1] + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1];
}
public int sumRegion(int R1, int C1, int R2, int C2) {
return (int)(dp[R2+1][C2+1] - dp[R2+1][C1] - dp[R1][C2+1] + dp[R1][C1]);
}
}
C++ Code:
(Jump to: Problem Description || Solution Idea)
class NumMatrix {
vector<vector<long>> dp;
public:
NumMatrix(vector<vector<int>>& M) {
int ylen = M.size() + 1, xlen = M[0].size() + 1;
dp = vector<vector<long>>(ylen, vector<long>(xlen, 0));
for (int i = 1; i < ylen; i++)
for (int j = 1; j < xlen; j++)
dp[i][j] = M[i-1][j-1] + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1];
}
int sumRegion(int R1, int C1, int R2, int C2) {
return (int)(dp[R2+1][C2+1] - dp[R2+1][C1] - dp[R1][C2+1] + dp[R1][C1]);
}
};
This content originally appeared on DEV Community and was authored by seanpgallivan
seanpgallivan | Sciencx (2021-05-12T09:56:03+00:00) Solution: Range Sum Query 2D – Immutable. Retrieved from https://www.scien.cx/2021/05/12/solution-range-sum-query-2d-immutable/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.