Apr 142017
 

Given a matrix of integers of order M*N and coordinates of a rectangular region in the matrix, write code to find the sum of all the elements in that rectangular region.

For example, if the input matrix is

And co-ordinated given are (3,4) and (6, 8), then they represent the below rectangular region whose Sum is 70.

Hence the output should be 70. How will your logic change if we need to compute sum of rectangular region many times for the same given matrix.

Solution

The brute-force solution is very simple, we just need to traverse in the rectangular region and keep adding each value to the sum.

int regionSum(int startI, int startJ, int endI, int endJ)
{
    int sum = 0;
    
    for(int i=startI; i<=endI; i++)
        for(int j=startJ; j<=endJ; j++)
            sum += arr[i][j];
    
    return sum;
}

This code takes O(n2) time in the worst case. If we are computing the sum again and again for the same matrix, then we can precompute the sum of rectangles and store them in a cache to reduce the time complexity of calculating region sum.

Solution-2: Precompute the cache

The idea is to have one more matrix of the same order in which cell (i,j) will store sum of all the cells in rectangular region starting from (0,0) till (i,j), both included. For the given matrix, this cache will look like

Now, for each cell we know the sum of rectangular region starting from (0,0) to that cell. Suppose we want to compute the sum of elements in the red rectangular region in the below matrix:

We do not know the sum of elements in this rectangle, but we know the sum of elements in all the below four rectangles, because their top-left cell is starting from (0,0)

   

   

Sum of elements in the red rectangle is equal to 123 + 4 (because elements in rectangle-4 are subtracted twice). It will be a constant time operation.

Below is the code of regionSum if cache is already precomputed.

int regionSum(int si, int sj, int ei, int ej)
{
    int sum = cache[ei][ej];
    
    if(si > 0)
        sum -= cache[si-1][ej];
    if(sj > 0)
        sum -= cache[ei][sj-1];
    if(si > 0 && sj > 0)
        sum += cache[si-1][sj-1];
    
    return sum;
}

What is left is the logic to precompute the cache. We use the O(n2) time algorithm to compute the cache. The logic is to first all all elements on the left side in row-i to each element in i’th row. If i’th row is

{1, 2, 0, 1, 2}

then after adding sum of values in cells on left side to each cell, this row will become

{1, 3, 3, 4, 6}

After this, the first row of cache is right, but other rows need to be updated. So we start from 2’nd row working backward in each row.

For each cell, we add the cell just just above it to the cell value.

void precomputeCache()
{
    // Store the sum of elements in individual rows
    for(int i=0; i<N; i++)
    {
        int sum = 0;
        for(int j=0; j<M; j++)
        {
            sum += arr[i][j];
            cache[i][j] = sum;
        }
    }
    
    for(int i=1; i<N; i++)
        for(int j=M-1; j>=0; j--)
            cache[i][j] += cache[i-1][j];
}

This is O(n^2) time algorithm. Below is the entire code of this solution:

#define N 8
#define M 10
int arr[N][M] = {
    {1, 2, 0, 3, 4, 1, 5, 8, 1, 0},
    {1, 5, 5, 2, 4, 9, 1, 2, 0, 1},
    {3, 8, 1, 3, 3, 7, 2, 1, 4, 9},
    {5, 2, 8, 6, 1, 0, 8, 4, 2, 3},
    {1, 4, 2, 5, 6, 3, 0, 1, 8, 1},
    {8, 2, 3, 5, 4, 1, 7, 2, 9, 3},
    {1, 7, 1, 0, 0, 1, 2, 7, 4, 3},
    {8, 5, 5, 9, 1, 2, 0, 3, 4, 2} };

int cache[N][M];

void precomputeCache()
{
    // Store the sum of elements in individual rows
    for(int i=0; i<N; i++)
    {
        int sum = 0;
        for(int j=0; j<M; j++)
        {
            sum += arr[i][j];
            cache[i][j] = sum;
        }
    }
    
    for(int i=1; i<N; i++)
    {
        for(int j=M-1; j>=0; j--)
        {
            cache[i][j] += cache[i-1][j];
        }
    }
}

int regionSum(int si, int sj, int ei, int ej)
{
    int sum = cache[ei][ej];
    
    if(si > 0)
        sum -= cache[si-1][ej];
    if(sj > 0)
        sum -= cache[ei][sj-1];
    if(si > 0 && sj > 0)
        sum += cache[si-1][sj-1];
    
    return sum;
}

int main(){
    precomputeCache();
    int t;
    int si, sj, ei, ej;
    cout<<"Enter the number of test cases:";
    cin>>t;
    for(int i=0; i<t; i++)
    {
        cin>>si>>sj>>ei>>ej;
        cout<<"\nTest Case #"<<i<<": "<<regionSum(si, sj, ei, ej);
    }
    return 0;
}

 

 

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)