TC: O(n*m) for creating the prefix[][] sum matrix, O(row1+row2) for calculating the sum of the given rectangle
SC: O(n*m) for using the prefix[][] sum matrix
class NumMatrix {
int prefix[][];
public NumMatrix(int[][] matrix) {
prefix = new int[matrix.length][matrix[0].length];
for(int i=0;i<matrix.length;i++){
int current = 0;
for(int j = 0;j<matrix[0].length;j++){
current+=matrix[i][j];
prefix[i][j] = current;
}
}
}
public int sumRegion(int row1, int col1, int row2, int col2) {
int sum =0;
for(int i =row1;i<=row2;i++){
int right = prefix[i][col2];
int left = (col1>0) ? prefix[i][col1-1] : 0;
sum+=right-left;
}
return sum;
}
}
/**
* Your NumMatrix object will be instantiated and called as such:
* NumMatrix obj = new NumMatrix(matrix);
* int param_1 = obj.sumRegion(row1,col1,row2,col2);
*/
Top comments (0)