🎨Now live: Try our Free AI Image Generation Feature

Description
The NumMatrix
problem requires implementing a class that can efficiently calculate the sum of elements within a submatrix of a given 2D matrix. The class should support multiple queries to sum the elements within any rectangular region defined by its top-left and bottom-right corners.
Intuition
To efficiently calculate the sum of elements within a submatrix, we can leverage a prefix sum technique. Instead of summing the elements in the submatrix directly each time a query is made, we precompute a prefix sum matrix. This matrix allows us to compute the sum of any submatrix in constant time by using the inclusion-exclusion principle.
Approach
- Prefix Sum Matrix Construction:
- Create a prefix sum matrix where each element
(i, j)
represents the sum of all elements in the submatrix from the top-left corner(0, 0)
to(i, j)
. - For each element(i, j)
in the original matrix, calculate the prefix sum as: [ \text{prefixSumMatrix}[i][j] = \text{matrix}[i][j] + \text{left} + \text{above} - \text{aboveLeft} ] whereleft
is the sum to the left,above
is the sum above, andaboveLeft
is the overlapping area. - Sum Region Calculation:
- To find the sum of elements in the submatrix defined by
(row1, col1)
and(row2, col2)
, use the prefix sum matrix: [ \text{sumRegion} = \text{prefixSumMatrix}[row2][col2] - \text{above} - \text{left} + \text{aboveLeft} ] whereabove
,left
, andaboveLeft
are the respective sums of the areas outside the submatrix. - Edge Cases:
- Handle cases where
row1
orcol1
are zero to avoid accessing out-of-bound indices.
Complexity
Time Complexity:
- The time complexity for constructing the prefix sum matrix is (O(m \times n)), where (m) is the number of rows and (n) is the number of columns.
- Each
sumRegion
query is answered in (O(1)) time due to the precomputed prefix sum matrix.
Space Complexity:
- The space complexity is (O(m \times n)) for storing the prefix sum matrix, where (m) is the number of rows and (n) is the number of columns.
Code
C++
class NumMatrix {
public:
NumMatrix(std::vector>& matrix) {
int rows = matrix.size();
int cols = matrix[0].size();
prefixSumMatrix.resize(rows, std::vector(cols, 0));
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
int left = (j > 0) ? prefixSumMatrix[i][j - 1] : 0;
int above = (i > 0) ? prefixSumMatrix[i - 1][j] : 0;
int aboveLeft = (i > 0 && j > 0) ? prefixSumMatrix[i - 1][j - 1] : 0;
prefixSumMatrix[i][j] = matrix[i][j] + left + above - aboveLeft;
}
}
}
int sumRegion(int row1, int col1, int row2, int col2) {
int total = prefixSumMatrix[row2][col2];
int above = (row1 > 0) ? prefixSumMatrix[row1 - 1][col2] : 0;
int left = (col1 > 0) ? prefixSumMatrix[row2][col1 - 1] : 0;
int aboveLeft = (row1 > 0 && col1 > 0) ? prefixSumMatrix[row1 - 1][col1 - 1] : 0;
return total - above - left + aboveLeft;
}
private:
std::vector> prefixSumMatrix;
};
Python
class NumMatrix:
def __init__(self, matrix):
rows = len(matrix)
cols = len(matrix[0])
self.prefixSumMatrix = [[0] * cols for _ in range(rows)]
for i in range(rows):
for j in range(cols):
left = self.prefixSumMatrix[i][j - 1] if j > 0 else 0
above = self.prefixSumMatrix[i - 1][j] if i > 0 else 0
aboveLeft = self.prefixSumMatrix[i - 1][j - 1] if i > 0 and j > 0 else 0
self.prefixSumMatrix[i][j] = matrix[i][j] + left + above - aboveLeft
def sumRegion(self, row1, col1, row2, col2):
total = self.prefixSumMatrix[row2][col2]
above = self.prefixSumMatrix[row1 - 1][col2] if row1 > 0 else 0
left = self.prefixSumMatrix[row2][col1 - 1] if col1 > 0 else 0
aboveLeft = self.prefixSumMatrix[row1 - 1][col1 - 1] if row1 > 0 and col1 > 0 else 0
return total - above - left + aboveLeft
Java
public class NumMatrix {
private int[][] prefixSumMatrix;
public NumMatrix(int[][] matrix) {
int rows = matrix.length;
int cols = matrix[0].length;
prefixSumMatrix = new int[rows][cols];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
int left = (j > 0) ? prefixSumMatrix[i][j - 1] : 0;
int above = (i > 0) ? prefixSumMatrix[i - 1][j] : 0;
int aboveLeft = (i > 0 && j > 0) ? prefixSumMatrix[i - 1][j - 1] : 0;
prefixSumMatrix[i][j] = matrix[i][j] + left + above - aboveLeft;
}
}
}
public int sumRegion(int row1, int col1, int row2, int col2) {
int total = prefixSumMatrix[row2][col2];
int above = (row1 > 0) ? prefixSumMatrix[row1 - 1][col2] : 0;
int left = (col1 > 0) ? prefixSumMatrix[row2][col1 - 1] : 0;
int aboveLeft = (row1 > 0 && col1 > 0) ? prefixSumMatrix[row1 - 1][col1 - 1] : 0;
return total - above - left + aboveLeft;
}
}
JavaScript
class NumMatrix {
constructor(matrix) {
this.matrix = matrix;
this.totalSum = [];
this.prefixSumMatrix(matrix)
}
prefixSumMatrix(matrix) {
for (let i = 0; i < matrix.length; i++) {
let rowSum = 0;
for (let j = 0; j < matrix[0].length; j++) {
const currNum = matrix[i][j];
matrix[i][j] = currNum + rowSum;
rowSum += currNum;
}
this.totalSum[i] = rowSum;
}
this.matrix = matrix;
}
// should work in O(1)
sumRegion(row1, col1, row2, col2) {
let regionSum = 0;
for (let row = row1; row <= row2; row++) {
const currRow = this.matrix[row];
const rowTotalSum = this.totalSum[row];
const leftSum = currRow[col1-1] || 0;
const rightSum = (rowTotalSum - currRow[col2]) || 0;
regionSum += rowTotalSum - (leftSum + rightSum);
}
return regionSum;
}
}