Category Archives: Dynamic Programming

Maximum size square sub matrix with all 1s in a binary matrix

Given a matrix of size M x N which contains only 0s and 1s, How do we find the largest square sub-matrix which contains all 1s.

For example in the following example, highlighted portion indicates a 3×3 square sub-matrix 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][j-1], temp[i-1][j], temp[i-1][j-1] ) + 1 
                 if matrix[i][j] = 1
           = 0 otherwise

 The logic behind this is to take the minimum of the left entry (i,j-1), top entry(i-1,j), diagonal entry(i-1,j-1) 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 sub-matrix 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][j-1],temp[i-1][j]);
minEntry = Math.min(minEntry, temp[i-1][j-1]);
 
                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;
}
}
}
//r-maxSize+1, c-maxSize+1 indicates starting point for required sub-matrix
System.out.println("Size of the Biggest square sub-matrix: "+ maxSize);
System.out.println("It starts at (" + (r-maxSize+1) + "," + (c-maxSize+1) + ")");
}
}

This method takes O(n2) time and O(m x n) space for the temp matrix.