In an interview I was asked if I was given an n*m matrix how to calculate the sum of the values in a given sub-matrix (defined by top-left, bottom-right coordinates).
I was told I could pre-process the matrix.
I was told the matrix could be massive and so could the sub-matrix so the algo had to be efficient. I stumbled a bit and wasn't told the best answer.
Anyone have a good answer?
Create a new matrix where entry (i,j) is the sum of elements in the original matrix that have lower or equal i and j. Then, to find the sum of the elements in the submatrix, you can just use a constant number of basic operations using the corners of the submatrix of your sum matrix.
In particular, find the corners top_left, bottom_left, top_right and bottom_right of your sum matrix, where the first three are just outside the submatrix and bottom_right is just inside. Then, your sum will be
bottom_right + top_left - bottom_left - bottom_right
This should work. You always have to go through each element in the submatrix to do the addition and this is the simplest way.
*note that the following code may not compile but it's right in pseudocode
struct Coords{
int x,y;
}
int SumSubMatrix(Coords topleft, Coords bottomright, int** matrix){
int localsum = 0;
for( int i = topleft.x; i <= bottomright.x; i++ ){
for(int j = topleft.y; j <= bottomright.y; j++){
localsum += matrix[i][j];
}
}
return localsum;
}
Edit: An alternative pre-processing method is to create another matrix from the original containing the row or column sums. Here's an example: Original:
0 1 4 2 3 2 1 2 7
Row Matrix:
0 1 5 2 5 7 1 3 10
Column Matrix:
0 1 4 2 4 6 3 6 13
Now, just take the endpoint x values and subtract the start point values, like so (for rows based):
for( int i = topleft.y; i >= bottomright.y; i++ ){
localsum += matrix2[bottomright.x][i] - matrix2[topleft.x][i];
}
Now, it's either O( n ) or O( m )