Calculate the sum of elements in a matrix efficiently

Question

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?

Answer 1

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 )

Answer 2

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

Answer 3

This is what Summed Area Tables are for. http://en.wikipedia.org/wiki/Summed_area_table

Your "preprocessing" step is to build a new matrix of the same size, where each entry is the sum of the sub-matrix to the upper-left of that entry. Any arbitrary sub-matrix sum can be calculated by looking up and mixing only 4 entries in the SAT.

EDIT: Here's an example.

For the initial matrix

0 1 4
2 3 2
1 2 7

The SAT is

0 1 5
2 6 12
3 9 22

If you want the sum of the lower-right 2x2 sub-matrix, the answer would be 22 + 0 - 3 - 5 = 14. Which is obviously the same as 3 + 2 + 2 + 7. Regardless of the size of the matrix, the sum of a sub matrix can be found in 4 lookups and 3 arithmetic ops. Building the SAT is O(n), similarly requiring only 4 lookups and 3 math ops per cell.