Find the largest square sub-matrix which is surrounded by all 1’s

Given a binary matrix, find the largest square sub-matrix which is surrounded by all 1’s.


 

For example, consider below binary matrix


1   1   1   1   1   1
1   0   1   1   0   1
0   1   1   0   0   1
1   1   1   1   1   1
1   0   0   1   0   1
1   0   1   1   0   0
1   0   1   0   1   1
1   1   1   0   1   1

 
The size of largest square sub-matrix in above binary matrix is 4. The largest square sub-matrix is formed by the cells (0, 2), (3, 2), (0, 5), and (3, 5).

 
The brute-force solution is to consider every square sub-matrix and check if it is surrounded by all 1’s. We keep track of dimensions of largest square sub-matrix seen and finally return it. The time complexity of this solution is O(M2 * N2) where M and N are dimensions of the matrix.

 
We can reduce the time complexity of the problem to O(M2 * N) by using O(M*N) extra space. The idea is to create two auxiliary matrices (say X and Y) where X[i][j] and Y[i][j] stores the number of continuous horizontal and vertical 1's ending at cell (i, j) respectively in the given matrix.

After filling both auxiliary matrices, we process each cell (i, j) starting from the last cell in the last row. For every cell (i, j), take the minimum of X[i][j] and Y[i][j] which could be the maximum length of right vertical line and bottom horizontal line of the square matrix ending at cell (i, j). The cell ending at current cell (i, j) would form a square sub-matrix if there exists a left vertical line and a top horizontal line of at-least the same length. We keep track of dimentions of largest square sub-matrix so far and return it when every cell is processed.

Here’s a C++ program that demonstrates it:

 

Download   Run Code

Output:

The largest square sub-matrix has length 4

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
Dima
Guest
Dima

The program returns 1 for the input array:

0001
0111
0101
1111

Is that OK?