CODEWITHSUNDEEP
algorithmmatrix
slippytoad
slippytoad

Reputation: 286

Calculate the sum of elements in a matrix efficiently

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?

Upvotes: 22

Views: 19669

Answers (5)

Nurlan Sofiyev
Nurlan Sofiyev

Reputation: 505

You can do it by Dynamic programming. Create matrix dp with size n*m. And for each i, j where 

1 <= i <= n , 1 <= j <= m 
dp[i][j] will be : 

dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + values[i][j]

And for each query we have lx, rx, ly, ry where lx and rx are top-left coordinates, ly and ry bottom-right coordinates of sub-matrix.

1 ≤ lxi ≤ rx ≤ n, 1 ≤ ly ≤ ry ≤ m

sum = dp[rx][ry]  - dp[lx - 1][ry] - dp[rx][ly - 1] + dp[lx-1][ly - 1]

Look at picture to understand how algorithm works. 

OD = dp[rx][ry], OB = dp[lx - 1][ry], OC = dp[rx][ly - 1], OA = dp[lx - 1][ly - 1]

enter image description here

Upvotes: 6

learner
learner

Reputation: 123

Below is a sample implementation in C using Summed Area Tables concept as explained in one of the answers above.

Python implementation for the same can be found at below link - http://www.ardendertat.com/2011/09/20/programming-interview-questions-2-matrix-region-sum/

#include<stdio.h>

int pre[3][3];

int arr[3][3] = {
                {0,1,4},
                {2,3,2},
                {1,2,7}
                };

void preprocess()
{
    for(int i=0;i<3;i++)
    {
        for(int j=0;j<3;j++)
        {
            if(i>0 && j>0)
            {
                 pre[i][j] = arr[i][j] + pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1];
            }
            else if(i>0 && j==0)
            {
                pre[i][j] = arr[i][j] + pre[i-1][j];
            }
            else if(j>0 && i==0)
            {
                pre[i][j] = arr[i][j] + pre[i][j-1];
            }
            else
            {
                pre[i][j] = arr[i][j];
            }                    
        }
    }
}

int subsum(int x1, int y1, int x2, int y2)
{
    preprocess();

    int ans = pre[x2][y2] - pre[x1-1][y2] - pre[x2][y1-1] + pre[x1-1][y1-1];
    return ans;
}

int main()
{            
    printf("%d\n",subsum(1,1,2,2));
    return 0;
}

Upvotes: 1

Alan
Alan

Reputation: 4933

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

The SAT is obtained using S(x,y) = a(x,y) + S(x-1,y) + S(x,y-1) - S(x-1,y-1),

where S is the SAT matrix and a is the initial matrix .

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.

Upvotes: 51

apandit
apandit

Reputation: 3344

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 )

Upvotes: 0

Peter
Peter

Reputation: 132227

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

Upvotes: 3

Related Questions