9

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.
Grijesh Chauhan
  • 57,103
  • 20
  • 141
  • 208
user2565192
  • 694
  • 1
  • 8
  • 19
  • This is a copy of a question presented on this blog more than two years ago: http://tech-queries.blogspot.com/search/label/Dynamic%20programming. – Martin Sep 17 '13 at 16:36

3 Answers3

11

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!

poorvank
  • 7,524
  • 19
  • 60
  • 102
  • 2
    ...and in order to find the maximum all-1s square sub-matrix of M, find the maximum entry in S, e.g. S[i][j]. This entry denotes the lower right corner of the maximum all-1s square sub-matrix of M of size S[i][j]. – Philip Jul 23 '13 at 07:30
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.

tmyklebu
  • 13,915
  • 3
  • 28
  • 57
-1

You can build an extra recursive function which gets as arguments a currect row and col, and looks for a square in any size from it.

From your other function, aftter the extra function returns a value, you have to make 2 calls: one from (row,col+1) and the other 1 from (row+1,col).

This is a backtracking usage, we check all the options.

user2600366
  • 84
  • 4