leetCode Question: Range Sum Query 2D - Immutable

Range Sum Query 2D - Immutable

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

Range Sum Query 2D
The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.

Example:
Given matrix = [
[3, 0, 1, 4, 2],
[5, 6, 3, 2, 1],
[1, 2, 0, 1, 5],
[4, 1, 0, 1, 7],
[1, 0, 3, 0, 5]
]

sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12
Note:
You may assume that the matrix does not change.
There are many calls to sumRegion function.
You may assume that row1 ≤ row2 and col1 ≤ col2.

Analysis

First glance at this problem give us an intuitive but less efficient solution: Loop through row1 to row2, loop through col1 to col2, add the matrix element one by one.

Given the condition that there are many function calls, we could start thinking of more efficient algorithm. Since the matrix does not change, we could possiblly store some information before the "sumRegion" calls, in order to help on the time complexity.

Firstly let's simplify the problem to the following description:
given a matrix, and one point, which is the bottom right corner, compute the sum of the region between (0, 0) and the point.

It's more intuitive to draw the figure below ( see (1) ):

From the figure, we could see the procedure to compute the sum of region by addition and subtraction.

Looking back to the original problem, it is then not hard to find out (figure (2) ):

sumRegion(row1, col1, row2, col2) = sum( (row2, col2) ) - sum( (row1-1, col2) ) - sum( (row2, col1-1) ) + sum( (row1-1, col1-1) )

Now, the only thing of which you may not get the idea is the initialization part. Actually it is not that hard but need more attention dealing with the indices. Specifically, we build a matrix of the same size, where every position [ i, j ] stores the sum of element between [0 , 0] and [ i, j ]. We are still using the procedure shown in figure (1):

For each position [ i, j ] in our sum matrix, we are checking [ i-1, j ] and [ i, j-1 ], the sum of [ i, j ] is:
m[ i, j ] = m[ i-1, j ] + m[ i, j-1 ] - m[ i-1, j-1 ], the procedure is shown below:

Code (C++)

class NumMatrix {

public:

NumMatrix(vector<vector<int>> matrix) {

nrow = matrix.size();

if (nrow == 0){ return; }

ncol = matrix[0].size();

matrix_sum = vector<vector<int>> (nrow+1, vector<int>(ncol+1, 0));

for (int i=1;i <= nrow; ++i){

for (int j=1;j <= ncol; ++j){

matrix_sum[i][j] = matrix_sum[i-1][j] + matrix_sum[i][j-1] - matrix_sum[i-1][j-1] + matrix[i-1][j-1];

}

}

}

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

int p1_i, p1_j, p2_i, p2_j, p3_i, p3_j, p4_i, p4_j;

p1_i = row1;

p1_j = col1;

p2_i = row1;

p2_j = col2 + 1;

p3_i = row2+1;

p3_j = col2+1;

p4_i = row2+1;

p4_j = col1;

return matrix_sum[p3_i][p3_j] - matrix_sum[p2_i][p2_j] - matrix_sum[p4_i][p4_j] + matrix_sum[p1_i][p1_j];

}

private:

vector<vector<int> > matrix_sum;

int nrow;

int ncol;

};

/**

* Your NumMatrix object will be instantiated and called as such:

* NumMatrix obj = new NumMatrix(matrix);

* int param_1 = obj.sumRegion(row1,col1,row2,col2);

*/

Code (Python)

class NumMatrix(object):

def __init__(self, matrix):

"""

:type matrix: List[List[int]]

"""

if len(matrix) == 0:

return

self.n_row = len(matrix)

self.n_col = len(matrix[0])

self.matrix_sum = [ [0 for i in range(self.n_col+1)] for j in range(self.n_row+1)]

for i in xrange(1, self.n_row+1):

for j in xrange(1, self.n_col+1):

self.matrix_sum[i][j] = self.matrix_sum[i-1][j] + self.matrix_sum[i][j-1] - self.matrix_sum[i-1][j-1] + matrix[i-1][j-1]

def sumRegion(self, row1, col1, row2, col2):

"""

:type row1: int

:type col1: int

:type row2: int

:type col2: int

:rtype: int

"""

p1_i, p1_j = row1, col1

p2_i, p2_j = row1, col2 + 1

p3_i, p3_j = row2 + 1, col2 + 1

p4_i, p4_j = row2 + 1, col1

return self.matrix_sum[p3_i][p3_j] + self.matrix_sum[p1_i][p1_j] - self.matrix_sum[p2_i][p2_j] - self.matrix_sum[p4_i][p4_j]

# Your NumMatrix object will be instantiated and called as such:

# obj = NumMatrix(matrix)

# param_1 = obj.sumRegion(row1,col1,row2,col2)