# Fast, with explanations - Partial sums, c++, 24ms (better than 100%)

• This is my solution, which relies on Dynamic Programming principles.
It uses O(n) space and runs in O(n) time, where 'n' is the size of the input (the size of the matrix).
Look at the following image and read the comments in the code:

``````class NumMatrix {
// partialSums is of the same size as matrix
// each cell, [row][col] has the sum of all the elements in the sub matrix (0,0),(row,col)
vector<vector<int>> partialSums;
public:
NumMatrix(vector<vector<int>> &matrix) : partialSums(matrix.size()) {
if (matrix.empty() || matrix[0].empty()) return;

// construct partialSums in a dynamic programming way
for (int row = 0; row<matrix.size(); row++) {
partialSums[row].resize(matrix[row].size());
for (int col = 0; col<matrix[row].size(); col++) {
// current cell
int sum = matrix[row][col];
// sum of sub matrix (0,0)-(row-1,col)
if (row > 0) sum += partialSums[row - 1][col];
// sum of sub matrix (0,0)-(row,col-1)
if (col > 0) sum += partialSums[row][col - 1];
// we actual counted the sub matrix (0,0)-(row-1,col-1) twice
if (row>0 && col>0) sum -= partialSums[row - 1][col - 1];
partialSums[row][col] = sum;
}
}
}

int sumRegion(int row1, int col1, int row2, int col2) {
// sum of sub matrix (0,0)-(row2,col2) -
//     all the colored areas, including the target sub matrix
int sum = partialSums[row2][col2];
// deduct the sum of sub matrix (0,0)-(row2,col1-1)
//     the green and purple areas
if (col1>0) sum -= partialSums[row2][col1 - 1];
// deduct the sum of sub matrix (0,0)-(row1-1,col2)
//     the blue and purple areas
if (row1>0) sum -= partialSums[row1 - 1][col2];
// since we deducted the purple area twice, you should re-add the purple area
if (col1>0 && row1>0) sum += partialSums[row1 - 1][col1 - 1];
return sum;
}
};
``````

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