Maximum size square sub-matrix with all 1s

Problem: Given a binary matrix consisting only 0s and 1s, find the maximum size square sub-matrix with all 1s.

Example: Consider the below matrix.

0 1 1 0 1
1 1 0 1 0
0 1 1 1 0
1 1 1 1 0
1 1 1 1 1
0 0 0 0 0

The maximum square sub-matrix with all ’1′ bits is from (2,1) to (4,3)
1 1 1
1 1 1
1 1 1

This is a classic Dynamic Programming problem. This question was asked in Google interview.

Solution:

We will use a auxiliary matrix S[][] of same size for memoization. S[i][j] represents size of the square sub-matrix with all 1s including M[i][j]. ‘i’ and ‘j’ will be the last row and column respectively in square sub-matrix.

Steps to construct S[][]

(1) First copy the first row and first column as it is from M[][] to S[][]

(2) And for the remaining entries as mentioned do the following:

If M[i][j] is 1 then
	S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1
Else /*If M[i][j] is 0*/
	S[i][j] = 0

(3) Find the maximum entry in S[][] and use it to construct the maximum size square sub-matrix.

For the given M[][] in above example, constructed S[][] would be:
0 1 1 0 1
1 1 0 1 0
0 1 1 1 0
1 1 2 2 0
1 2 2 3 1
0 0 0 0 0

The value of maximum entry in above matrix is 3 and coordinates of the entry are (4, 3). Using the maximum value and its coordinates, we can find out the required sub-matrix.

void printMaxSubSquare(bool M[R][C])
{
  int i,j;
  int S[R][C];
  int maximum, i_index_max, j_index_max; 
  maximum = S[0][0]; i_index_max = 0; j_index_max = 0;
  
  /* Set first column of S[][]*/
  for(i = 0; i < R; i++)
     S[i][0] = M[i][0];
  
  /* Set first row of S[][]*/    
  for(j = 0; j < C; j++)
     S[0][j] = M[0][j];
      
	for(i = 1; i < R; i++)
	{
		for(j = 1; j < C; j++)
		{
			if(M[i][j] == 1) 
				S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1;
			else
				S[i][j] = 0;
		}    
	} 
   
  
	for(i = 0; i < R; i++)
	{
		for(j = 0; j < C; j++)
		{
			if(maximum < S[i][j])
			{
				maximum = S[i][j];
				i_index_max = i; 
				j_index_max = j;
			}        
		}                 
	}     
   
	printf("Maximum size sub-matrix is: \n");
	for(i = i_index_max; i > i_index_max - maximum; i--)
	{
		for(j = j_index_max; j > j_index_max - maximum; j--)
		{
			printf("%d ", M[i][j]);
		}  
		printf("\n");
	}  
}     

Complexity:
Time Complexity: O(m*n) where m is number of rows and n is number of columns in the given matrix.
Space Complexity: O(m*n) where m is number of rows and n is number of columns in the given matrix.