Maximum size square sub-matrix with all 1 s, Recusively

Question

Given a binary matrix, find out the maximum size square sub-matrix with all 1 s, Recusively

For example, consider the below binary matrix.
(Source:- geeksforgeeks

   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 set bits is

1  1  1
1  1  1
1  1  1

As we know it's general solution is with DP, but here i am interested in Recursive Approach

Comments

Any solution in general on matrix is o(n^2) now DP provides the solution of o(n^2). I think if we take the recursive approach then we need to again use DP on the submatrix and the approach become very costly.

---

Sir..you are right, but looking for approach because DP is common for this question.

---

#include <stdio.h>
#include <stdlib.h>
#define alloc(type,size) (type*)malloc(size*sizeof(type))

int min(int a,int b){
    return a < b ? a:b;
}

int max(int a,int b){
    return a>b ? a:b ;
}

int findSize(int **arr,int i,int j,int val,int *incl){
    if (i<0 || j<0 ) { *incl = 0 ; return 0; }
    int m1,m2,m3,in1,in2,in3;
    m1 = findSize(arr,i-1,j-1,val,&in1);
    m2 = findSize(arr,i,j-1,val,&in2);
    m3 = findSize(arr,i-1,j,val,&in3);
   
    *incl = arr[i][j]==val  ? 1+min(in1,min(in2,in3)) : 0;
    int excl = max(m1,max(m2,m3));
    return max(*incl,excl);
}

main(){
    int m=5,n=6,*arr[m],i,j,bin[]={
        1,1,1,1,0,1,
        1,0,0,0,0,1,
        1,0,0,0,0,1,
        1,0,0,0,0,1,
        1,1,1,0,1,1
    },k;
    for (i=0;i<m;i++) arr[i] = alloc(int,n);
    for (i=0,k=0;i<m;i++)
        for (j=0;j<n;j++) arr[i][j] = bin[k++];
    for (i=0;i<m;i++,printf("\n"))
     for (j=0;j<n;j++) printf("%d ",arr[i][j]);
     int incl,val=0;
     printf("Max Size of %d submatrix : %d\n",val,findSize(arr,m-1,n-1,val,&incl));
   
   
}

In this 'incl' is used to find the maxsize submatrix which includes arr[i][j] element , the other is 'excl' which excludes the current element .
So we are returning the maximum of  inclusive and exclusive sizes .
Note that while you calculate the inclusive size , only consider the inclusive values that you get on the  recursive calls . Expression for finding the inclusive size is similar to the one in DP approach .Hope this helps you..

Answer 1

typedef struct mat
{
    int n, r, c;
}matParm;

matParm sub_mat;    // Global Variable 

/* Call from main function */

    if( row > col)
        for (i = 0; i < row - col; i++)
            find_sqr_mat (matrix, i, 0, col);
    else if (col > row)
        for (i = 0; i <  col - row ; i++)
            find_sqr_mat (matrix, 0, i, row);
    else
        find_sqr_mat (matrix, 0, 0, col);

/* Print the out put matrix */

printf("\n Largest Sub Square Matrix\n");
printf("Row = %d  Col = %d  N = %d\n",sub_mat.r, sub_mat.c, sub_mat.n);
for (i = sub_mat.r; i < sub_mat.r + sub_mat.n; i++)
{
    printf("\n\n");
    for (j = sub_mat.c; j < sub_mat.c + sub_mat.n; j++)
        printf("%d    ", matrix[i][j]);
}

/* Function to find the largest squar matrix */

matParm * find_sqr_mat(int **M, int row, int col, int N)
{
  int n = 0;
  matParm * tempparm;
  matParm *tempparm1, *tempparm2, * tempparm3, * tempparm4;
  tempparm = (matParm *)malloc(sizeof(matParm));
  if ( N==1 )
  {
    if(M[row][col] == 1)
    {
        tempparm->n = N;
        tempparm->r = row;
        tempparm->c = col;
    }
    else
    {
        tempparm->n = 0;
        tempparm->r = 0;
        tempparm->c = 0;
    }
  }
  else
  {
    tempparm1 = find_sqr_mat(M, row, col, N-1);
    tempparm2 = find_sqr_mat(M, row+1, col, N-1);
    tempparm3 = find_sqr_mat(M, row, col+1, N-1);
    tempparm4 = find_sqr_mat(M, row+1, col+1, N-1);
    if((tempparm1 && tempparm2 && tempparm3 && tempparm4) &&
       (tempparm1->n == tempparm2->n) &&
       (tempparm2->n == tempparm3->n) &&
       (tempparm3->n == tempparm4->n) &&
       (tempparm4->n == N-1))
    {
        tempparm->n = N;
        tempparm->r = row;
        tempparm->c = col;

        if (sub_mat.n < N)
        {
            sub_mat.n = N;
            sub_mat.r = row;
            sub_mat.c = col;
        }
        free(tempparm1);
        free(tempparm2);
        free(tempparm3);
        free(tempparm4);

        return tempparm;
    }
    else
    {
        return NULL;
    }
    free(tempparm1);
    free(tempparm2);
    free(tempparm3);
    free(tempparm4);
  }
  return tempparm;
}

Hi,

I have tested it for some examples.
Please let me know if any test case is failed.

Answer 2

Dont know the recursive approach, see of this helpful (DP approach)

This is a classic Dynamic Programming problem. Lets calculate the maximum size square sub-matrix as we traverse the original matrix M[][]. 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.

How to calculate S[i][j]:
We should note that if M[i][j] is '0' then S[i][j] will obviously be '0'. If M[i][j] is '1' then S[i][j] depends on earlier values.

If M[i][j] is '1' then it will contribute to the all 1s square sub-matrix ending at either M[i][j-1] or M[i-1][j] or M[i-1][j-1]. If we visualize the conditions then, we will see:
S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1

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");
    }  
}     

Comments

Sir, i have already attempted successfully  this question by DP...i was  trying to solve by Recursion (this is where i am interested right now).

---

I doubt if it is possible, I can not think of any recursive solution.

---

Any reason that it can't solved by recursively...(as per my knowledge this question has already been asked in one of the interview)

Answer 3

Check this, but applicable when input matrix is square. But you can make matrix square by adding 0 to the column or rows to make it square.

#include<iostream> 
#define SIZE 5 

using namespace std; 

int checkthis(int a[][SIZE], int n, int size, int x, int y) 
{ 
    int i=0; 
    int j=y; 

    for(i=x;i<=x+size-1;i++) 
        if(a[i][j]==0) 
            return 0; 

    j=y+size-1; 
    for(i=x;i<=x+size-1;i++) 
        if(a[i][j]==0 ) 
            return 0; 

    j=x; 
    for(i=y;i<=y+size-1;i++) 
        if(a[j][i]==0 ) 
            return 0; 

    j=x+size-1; 
    for(i=y;i<=y+size-1;i++) 
        if(a[j][i]==0 ) 
            return 0; 

    return 1; 
} 

int findsquares(int a[][SIZE], int n, int size, int &x, int &y ) 
{ 
    int ret = 0; 
    for(int i =0; i<=n-size; i++) 
        for(int j=0; j<=n-size; j++) 
        { 
            ret = checkthis(a,n,size,i,j); 
            if(ret == 1) 
            { 
                x=i; 
                y=j; 
                return size; 
            } 
        } 
    return 0; 
} 

int main() 
{ 
    int a[SIZE][SIZE] = {{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}};

    int x=-1,y=-1; 
    int k=0; 

    for(int i=SIZE;i>=1;i--) 
    { 
        k=findsquares(a,SIZE,i,x,y); 
        if(k!=0) break; 
    } 

    cout<<"\nStart Co-ordinates:"<<x<<","<<y<<" size:"<<k<<"\n"; 

    for(int i=0;i<k;i++) 
    { 
        for(int j=0;j<k;j++) 
        { 
            cout << a[x+i][y+j] <<" ";
        } 
        cout << "\n";
    }

    return 0; 
}

Comments

Failing here...
{{0, 1, 1, 0, 1},
  {1, 1, 0, 1, 0},
   {0, 1, 1, 1, 0},
   {1, 1, 0, 1, 0},
    {1, 1, 1, 1, 1

---

yes you are right this will not work, may be luv is right...

---

check if you can do something to the checkthis function and making it recursive is simple i.e. you need to make the following code recursive...
    for(int i=SIZE;i>=1;i--)
    {
        k=findsquares(a,SIZE,i,x,y);
        if(k!=0) break;
    }

---

If you will refer my solution. you will find the recursive solution. :)