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


The largest square sub-matrix has length 4

1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)


Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂

Leave a Reply

newest oldest most voted
Notify of

The program returns 1 for the input array:


Is that OK?