top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

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

+4 votes
3,640 views

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

posted Dec 28, 2013 by Atiqur Rahman

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button
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..

3 Answers

+2 votes
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 May 8, 2014 by Vikas Upadhyay
+1 vote

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");
    }  
}     
answer Dec 28, 2013 by Luv Kumar
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)
–1 vote

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; 
}
answer Dec 28, 2013 by Salil Agrawal
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. :)
Similar Questions
0 votes

suppose

A(n,m) = 
1 2 3         
4 5 6                            
7 8 9

and 

B(p, q) = 
1 1
1 1

What is best method to find min of square of difference of sub-matrices of A and B e.g.

sub-matrices of A =

1 2    |     2 3   |    4 5    |   5 6
3 4    |     5 6   |    7 8    |   8 9

Difference of first sub-matrix of A with B =

(1-1)  (2-1)    = |     0 1
(3-1)  (4-1)      |     2 3

sum of square of elements = 0*0 + 1*1 + 2*2 + 3*3 = 14

similar steps for other sub-matrices of A

Please suggest looking for an alternate method or algorithm which has time complexity less than O(n*m*p*q)

+3 votes

Input: arr[] = {5, 5, 10, -10, -20, 40, 50, 35, -20, -50}
Output: 125 (40, 50, 35)

+6 votes

Given a matrix with 1s and 0s, please find the number of groups of 1s. A group is defined by horizontally or vertically adjacent 1s.

...