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

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(M ^{2} * N^{2})` where M and N are dimensions of the matrix.

We can reduce the time complexity of the problem to `O(M ^{2} * 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:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 |
#include <iostream> using namespace std; // Dimensions of input matrix M X N #define M 8 #define N 6 // Function to find the largest square sub-matrix which is surrounded by all 1's int findLargestSquareSubMatrix(short mat[][N]) { // create two auxiliary matrix filled with all 0's of size M X N int X[M][N] = {}; int Y[M][N] = {}; // update the auxiliary matrix X[][] and Y[][] with // number of continuous 1's ending at the cell for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { if (mat[i][j]) { if (i == 0) { Y[i][j] = 1; } else { Y[i][j] = Y[i - 1][j] + 1; } if (j == 0) { X[i][j] = 1; } else { X[i][j] = X[i][j - 1] + 1; } } } } // to keep track of the largest square sub-matrix int max_length = 0; // process each cell (i, j) of the auxiliary matrix starting from the // last cell in the last row for (int i = M - 1; i >= 1; i--) { for (int j = N - 1; j >= 1; j--) { // The minimum of X[i][j] and Y[i][j] would be the length of // right vertical line and bottom horizontal line of the // square matrix ending at cell (i, j) int len = min(X[i][j], Y[i][j]); while (len) { // the cell ending at current cell (i, j) forms a square // sub-matrix if there exists a left vertical line and a // top horizontal line of at-least length 'len' bool isSquare = Y[i][j - len + 1] >= len && X[i - len + 1][j] >= len; // check if square ending at current cell is largest so far if (isSquare && max_length < len) { max_length = len; } // reduce the length by 1 to check for smaller squares ending // at current cell len--; } } } return max_length; } // main function int main() { short mat[M][N] = { { 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 } }; cout << "The size of largest square sub-matrix is " << findLargestSquareSubMatrix(mat); return 0; } |

`Output:`

The largest square sub-matrix has length 4

**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

The program returns 1 for the input array:

00010111

0101

1111

Is that OK?

There was some minor problem with the code, we have fixed it. Thanks for bringing this to our notice. Happy coding 🙂