find the maximum size of square sub matrix with all 1’s in a binary matrix

Program to find the maximum size of square sub matrix with all 1’s in a binary matrix is discussed here. Given a binary matrix, find the maximum size square sub-matrix with all 1’s.

For example, consider the matrix given below.

Input:

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

Output:

Maximum square sub-matrix:

1     1     1     
1     1     1       
1     1     1    

Algorithm to find the maximum size of square sub matrix with all 1’s in a binary matrix

  • Define and initialize subMat whose order is same as the given matrix.
  • Copy first row and first column of the given matrix to subMat.
  • for all row i = (1 to n), do
  • for all column j = (1 to n), do          
  • if matrix[i, j] = 1, then            
  • subMat[i, j] = 1 + minimum of subMat[i, j1]            
  • and subMat[i1, j1]          
  • else            
  • subMat[i, j] = 0
  • maxSize = subMat[0, 0], iMax = 0 and jMax = 0  
  • for all row i and column j, do      
  • if maxSize < subMat[i, j], then        
  • maxSize = subMat[i, j]          
  • iMax = i, jMax = j   
  • print sub matrix from row = iMax to (iMax  maxSize), and column jMax to (jMax  maxSize)

Program to find the maximum size of square sub matrix with all 1’s in a binary matrix is given below.

/* C program to find the maximum size of square sub matrix with all 1’s in a binary matrix */

#include
#define ROW 6
#define COL 5

// Global declaration of the matrix
int matrix[ROW][COL] = {
{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}
};

/* Function to find the minimum value */
int min(int a, int b, int c)
{
return ((a<b?a:b))?((a<c)?a:c):((b<c)?b:c);
}

void sub_matrix_with_one()
{
int subMat[ROW][COL];
int maxSize, iMax, jMax;

for(int i = 0; i < ROW; i++) //copy first row of matrix to sub matrix
subMat[i][0] = matrix[i][0];

for(int j = 0; j < COL; j++) //copy first column of matrix to sub matrix
subMat[0][j] = matrix[0][j];

for(int i = 1; i < ROW; i++)
{
for(int j = 1; j < COL; j++)
{
if(matrix[i][j] == 1) //find minimum of left, top and diagonal element + 1
subMat[i][j] = min(subMat[i][j-1], subMat[i-1][j], subMat[i-1][j-1]) + 1;
else
subMat[i][j] = 0; //if item is 0, put only 0
}
}

maxSize = subMat[0][0]; iMax = 0; jMax = 0;
for(int i = 0; i < ROW; i++)
{ //find the order of sub square matrix

for(int j = 0; j < COL; j++)
{
if(maxSize < subMat[i][j])
{

maxSize = subMat[i][j];
iMax = i;
jMax = j;
}
}
}

printf(“Subsquare matrix: “);
printf(“\n”);
for(int i = iMax; i > iMax – maxSize; i–)
{
//print the submatrix using max size
for(int j = jMax; j > jMax – maxSize; j–)
{
printf(“%d “,matrix[i][j]);
}
printf(“\n”);
}
}

int main()
{
sub_matrix_with_one();
}

/* C++ program to find the maximum size of square sub matrix with all 1’s in a binary matrix */

#include<iostream>
#define ROW 6
#define COL 5
using namespace std;

// Global declaration of the matrix
int matrix[ROW][COL] = {
{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}
};

/* Function to find the minimum value */
int min(int a, int b, int c)
{
return ((a<b?a:b))?((a<c)?a:c):((b<c)?b:c);
}

void sub_matrix_with_one()
{
int subMat[ROW][COL];
int maxSize, iMax, jMax;

for(int i = 0; i < ROW; i++) //copy first row of matrix to sub matrix
subMat[i][0] = matrix[i][0];

for(int j = 0; j < COL; j++) //copy first column of matrix to sub matrix
subMat[0][j] = matrix[0][j];

for(int i = 1; i < ROW; i++)
{
for(int j = 1; j < COL; j++)
{
if(matrix[i][j] == 1) //find minimum of left, top and diagonal element + 1
subMat[i][j] = min(subMat[i][j-1], subMat[i-1][j], subMat[i-1][j-1]) + 1;
else
subMat[i][j] = 0; //if item is 0, put only 0
}
}

maxSize = subMat[0][0]; iMax = 0; jMax = 0;
for(int i = 0; i < ROW; i++)
{ //find the order of sub square matrix

for(int j = 0; j < COL; j++)
{
if(maxSize < subMat[i][j])
{

maxSize = subMat[i][j];
iMax = i;
jMax = j;
}
}
}

cout << “Subsquare matrix: “<<endl;
for(int i = iMax; i > iMax – maxSize; i–)
{
//print the submatrix using max size
for(int j = jMax; j > jMax – maxSize; j–)
{
cout << matrix[i][j]<<” “;
}
cout << endl;
}
}

int main()
{
sub_matrix_with_one();
}

Output:

find the maximum size of square sub matrix with all 1's in a binary matrix