Given a matrix of size M x N which contains only 0s and 1s, How do we find the largest square submatrix which contains all 1s.
For example in the following example, highlighted portion indicates a 3×3 square submatrix with all 1s.
1

0

0

1

1

0

0

1

1

1

1

1

0

1

1

1

1

0

1

0

1

1

1

0

0

1

0

1

1

0

1

1

1

0

0

1

We can solve this problem using Dynamic programming approach.
We take a temporary matrix with the same size as that of original matrix. The entries of the temporary matrix are calculated using the following method.
The first row and first column of temp matrix will be same as that of original matrix.
Remaining entries are calculated using the following formula
temp[i][j] = Min( temp[i][j1], temp[i1][j], temp[i1][j1] ) + 1
if matrix[i][j] = 1
= 0 otherwise
The logic behind this is to take the minimum of the left entry (i,j1), top entry(i1,j), diagonal entry(i1,j1) and add 1 if the current entry is 1 otherwise fill zero for that entry.
Let us assume temp[i][j] represents the bottom right corner of the largest square submatrix with all 1s. The value also indicates the size of that matrix.
1 0 0 1 1 0
0 1 1 1 2 0
0 1 2 2 2 1
1 0 1 2 3 0
0 1 1 0 1 1
For example, the above temp matrix indicates that there is a 3×3 sub matrix exists with all 1s. It starts from index (1,2).
Here is the Java code
/**
* Created with IntelliJ IDEA.
* User: Ravi
* Date: 9/30/13
* Time: 6:57 AM
* To change this template use File  Settings  File Templates.
*/
public class Main {
public static void main(String[] args)
{
int nRows = 5, nCols = 6;
int[][] boolMatrix = {
{1,0,0,1,1,0},
{0,1,1,1,1,0},
{0,1,1,1,1,1},
{1,0,1,1,1,0},
{0,1,1,0,1,1}
};
printMaxSubMatrixIndex(boolMatrix, nRows, nCols);
}
public static void printMaxSubMatrixIndex(int[][] bMatrix, int nRows, int nCols)
{
int[][] temp = new int[nRows][nCols];
int i,j;
//copy the first column as it is
for( i = 0; i < nRows; i++ )
{
temp[i][0] = bMatrix[i][0];
}
//copy the first row as it is
for( i = 0; i < nCols; i++ )
{
temp[0][i] = bMatrix[0][i];
}
//calculate temp table
for( i = 1; i < nRows; i++ )
{
for( j = 1; j < nCols; j++ )
{
int minEntry = Math.min(temp[i][j1],temp[i1][j]);
minEntry = Math.min(minEntry, temp[i1][j1]);
if( bMatrix[i][j] == 1)
temp[i][j] = minEntry+1;
else
temp[i][j] = 0;
}
}
//iterate through the temp matrix to get the max size and indices
int maxSize = 0;
int r = 1;
int c = 1;
for( i = 0; i < nRows; i++ )
{
for( j = 0; j < nCols; j++ )
{
if( maxSize < temp[i][j] )
{
maxSize = temp[i][j];
r = i;
c = j;
}
}
}
//rmaxSize+1, cmaxSize+1 indicates starting point for required submatrix
System.out.println("Size of the Biggest square submatrix: "+ maxSize);
System.out.println("It starts at (" + (rmaxSize+1) + "," + (cmaxSize+1) + ")");
}
}
This method takes O(n^{2}) time and O(m x n) space for the temp matrix.