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 c
alculated 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(n²) time and O(m x n) space for the temp matrix.

Leave a Reply Cancel reply