Maximum size square sub-matrix with all 1s [duplicate]

Question

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

For example, consider the below binary 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 set bits is

1  1  1
1  1  1
1  1  1

I searched the web for solutions and I found a relation to construct an auxiliary matrix:

 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

1. Where M[][] is the original matrix and s[][] is the auxiliary matrix?
2. What does this relation signify?
3. And how is it helpful.

Answer 1

This is a classic Dynamic Programming problem. And u haven't mentioned the entire algorithm which is as follows:

To construct the auxiliary array we have to do the following:

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

2. And for the remaining entries as u 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 submatrix

What does this relation signify?

To find the maximum square, we need to find the minimum extension of 1s in different directions and add 1 to it to form the length of square ending at present case.

so as for your case 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

If we just take minimum of these i.e S[i][j-1], S[i-1][j] , it takes care of left and top direction.However, we also need to make sure that there are 1's in top left corner of perspective square. S[i-1][j-1], by definition, contains a max square at position i-1, j-1, whose top left corner ,puts an upper limit on how up and left we can get. So, we need to consider that as well.

Hope this helps!

Answer 2

You can do this in linear time.

Claim: I can build a data structure in linear time that lets me check, in constant time, whether an arbitrary rectangle is full of 1's.

Proof: Partial sums; take S[i][j] to be the total number of 1's above and to the left of (i, j). The number of ones in the rectangle between (a,b) and (c,d), provided (a,b) is above and left of (c,d), is S[c][d] + S[a][b] - S[a][d] - S[b][c].

Now it's a simple scan over the array:

size = 1;
For i = 0 to m-size {
  For j = 0 to n-size {
    If S[i+size][j+size] - S[i][j+size] - S[i+size][j] + S[i][j] == size*size {
      size++; j--; continue;
    }
  }
}

At the end, size is one greater than the largest 1-full square.