# C++ solution beats 100% O(n^2) time and O(1) space

• ``````//Idea: Sum of a column sum[m..n][j] is sum[0...n][j]-matrix[0...m-1][j]
vector<vector<int>>* matrix_;
NumMatrix(vector<vector<int>> &matrix) {
// Each cell stores its vale + elements in the same col above it

// First row is unchanged
int row = matrix.size();
for (int i = 1; i < row; ++i) {
int col = matrix[i].size();
for (int j = 0; j < col; ++j) {
matrix[i][j] = matrix[i][j] + matrix[i-1][j];
}
}
matrix_ = &matrix;
}

// Sum of a column [m..n][j] is matrix[n][j]-matrix[m-1][j]
int sumRegion(int row1, int col1, int row2, int col2) {
int row = matrix_->size(), col = 0;
if (row > 0) {
col = (*matrix_)[0].size();
}
if (row == 0 || col == 0) {
return 0;
}
if (row1 < 0 || row2 >= row || col1 < 0 || col2 >= col) {
return 0;
}

int sum = 0;
for (int j = col1; j <= col2; ++j) {
int above = 0;
if (row1 > 0) {
above = (*matrix_)[row1-1][j];
}
sum += (*matrix_)[row2][j] - above;
}
return sum;
}``````

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