Make delicious recipes!

Finding sum of sub-matrix millions of times



Problem: Given a two-dimensional array of integers, how to optimize finding the sum of its submatrix?
The submatrix is specified by two points (x1,y1) and (x2,y2).
And the submatrix sum is required to be found millions of times for many sub-matrices of this matrix.



Solution: Simplest solution to find submatrix sum is to just run two loops - from x1 to x2 and from y1 to y2.
However, since the submatrix sum can be demanded millions of times, then there must be some way to optimize this.

A good idea is to calculate the submatrix sum at every point in the original matrix and save it in a separate matrix such that sum[i][j] gives the sum of submatrix from (0,0) to (i,j).
Then the submatrix sum between any two points (x1,y1) and (x2,y2) is simply given by the following formula:

    sum[x2][y2] + sum[x1][y1] - sum[x1][y2] - sum[x2][y1]

Sum matrix can be found as follows:


void createSumMatrix (int [][]matrix, int [][]sum)
{
    for (int i = 0; i < matrix.length; i++)
    {
        for (int j=0; j<matrix[i].length; j++)
        {
            sum[i][j] = matrix[i][j];
            if (i > 0)
                sum[i][j] += sum [i-1][j];
            if (j > 0)
            {
                sum[i][j] += sum [i][j-1];
                if (i > 0)
                    sum[i][j] -= sum[i-1][j-1]; // because this is added twice in above two additions
            }
        }
    }
}


// driver program to test the sum function
void testSum () 
{
    int [][] matrix = {
        {1, 2, 4}, 
        {7, 4, 3}, 
        {2, 6, 5}, 
    };

    int sum [][] = new int [3][3];

    createSumMatrix (matrix, sum);

    for (int i = 0; i < matrix.length; i++)
    {
        for (int j=0; j<matrix[i].length; j++)
        {
            System.out.print(sum[i][j] + ", ");
        }
        System.out.println ();
    }
}

/*
Sum matrix for above input is:
    1    3   7
    8   14  21
    10  22  34
*/






Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal