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:

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
*/

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