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 3x3 square submatrix with all 1s.
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 3x3 sub matrix exists with all 1s. It starts from index (1,2).
Here is the Java code
This method takes O(n^{2}) time and O(m x n) space for the temp matrix.
For example in the following example, highlighted portion indicates a 3x3 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 3x3 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.