Question

link

Given a binary matrix, 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 size 9. Note we only find square, not rectangles! (this makes it much easier)

Solution

Since square only, we can use DP. Quoted answer below:

Let the given binary matrix be M[R][C]. The idea of the algorithm is to construct an auxiliary size matrix S[][] in which each entry S[i][j] represents size of the square sub-matrix with all 1s including M[i][j] where M[i][j] is the rightmost and bottommost entry in sub-matrix.

1. Construct a sum matrix S[R][C] for the given M[R][C].

2. Copy first row and first columns as it is from M[][] to S[][]

3. For other entries, use following expressions to construct S[][]

         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