# C++ solution: O(1) for sumRegion function

• My idea is in constructor we build a sum_matrix in which element (i, j) is the sum of sub-matrix (0, 0)-->(i, j). Then for sumRegion we could directly calculate the sum of sub-matrix (row1, col1)-->(row2, col2). Not sure this is the fastest solution, just for your reference:

class NumMatrix {
public:
NumMatrix(vector<vector<int>> &matrix) {
sum_matrix = matrix;
if(matrix.empty()) return;
for(int i = 0; i < matrix.size() - 1; ++i)
sum_matrix[i + 1][0] += sum_matrix[i][0];
for(int j = 0; j < matrix[0].size() - 1; ++j)
sum_matrix[0][j + 1] += sum_matrix[0][j];
for(int i = 1; i < matrix.size(); ++i)
{
for(int j = 1; j < matrix[0].size(); ++j)
{
sum_matrix[i][j] += sum_matrix[i - 1][j] + sum_matrix[i][j - 1] - sum_matrix[i - 1][j - 1];
}
}
}

int sumRegion(int row1, int col1, int row2, int col2) {
if(sum_matrix.empty()) return 0;
int all = sum_matrix[row2][col2];
int left = (col1 == 0) ? 0 : sum_matrix[row2][col1 - 1];
int top = (row1 == 0) ? 0 : sum_matrix[row1 - 1][col2];
int mid = (row1 == 0 || col1 == 0) ? 0 : sum_matrix[row1 - 1][col1 - 1];
return all - left - top + mid;

}
private:
vector<vector<int>> sum_matrix;//(i, j): (0,0)(i,j) sum
};

• I tried the following and got a "Time Limit Exceeded" message.

any thought on the following written in java?

code:
public class NumMatrix {

private static int[][] wMatrix;

public NumMatrix(int[][] matrix) {
wMatrix = matrix;
}

public int sumRegion(int row1, int col1, int row2, int col2) {

int sum = 0;

if (wMatrix.length > 0)
{
for(int r=row1;r<row2 || r==row2 ;r++)
{
int a[] = Arrays.copyOfRange(wMatrix[r], col1, col2);
sum  += IntStream.of(a).sum();
}
}

return sum;
}

}

• Should you compute wMatrix in the constructor?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.