Given a matrix of ‘O’ and ‘X’, find the largest subsquare surrounded by ‘X’

Given a matrix where every element is either ‘O’ or ‘X’, find the largest subsquare surrounded by ‘X’. 
In the below article, it is assumed that the given matrix is also a square matrix. The code given below can be easily extended for rectangular matrices.

Examples: 

Input: mat[N][N] = { {'X', 'O', 'X', 'X', 'X'},
                     {'X', 'X', 'X', 'X', 'X'},
                     {'X', 'X', 'O', 'X', 'O'},
                     {'X', 'X', 'X', 'X', 'X'},
                     {'X', 'X', 'X', 'O', 'O'},
                    };
Output: 3
The square submatrix starting at (1, 1) is the largest
submatrix surrounded by 'X'

Input: mat[M][N] = { {'X', 'O', 'X', 'X', 'X', 'X'},
                     {'X', 'O', 'X', 'X', 'O', 'X'},
                     {'X', 'X', 'X', 'O', 'O', 'X'},
                     {'X', 'X', 'X', 'X', 'X', 'X'},
                     {'X', 'X', 'X', 'O', 'X', 'O'},
                    };
Output: 4
The square submatrix starting at (0, 2) is the largest
submatrix surrounded by 'X'

A Simple Solution is to consider every square submatrix and check whether is has all corner edges filled with ‘X’. The time complexity of this solution is O(N⁴).
We can solve this problem in O(N³) time using extra space. The idea is to create two auxiliary arrays hor[N][N] and ver[N][N]. The value stored in hor[i][j] is the number of horizontal continuous ‘X’ characters till mat[i][j] in mat[][]. Similarly, the value stored in ver[i][j] is the number of vertical continuous ‘X’ characters till mat[i][j] in mat[][]. 

Example:

mat[6][6] =  X  O  X  X  X  X
             X  O  X  X  O  X
             X  X  X  O  O  X
             O  X  X  X  X  X
             X  X  X  O  X  O
             O  O  X  O  O  O

hor[6][6] = 1  0  1  2  3  4
            1  0  1  2  0  1
            1  2  3  0  0  1
            0  1  2  3  4  5
            1  2  3  0  1  0
            0  0  1  0  0  0

ver[6][6] = 1  0  1  1  1  1
            2  0  2  2  0  2
            3  1  3  0  0  3
            0  2  4  1  1  4
            1  3  5  0  2  0
            0  0  6  0  0  0

Once we have filled values in hor[][] and ver[][], we start from the bottommost-rightmost corner of matrix and move toward the leftmost-topmost in row by row manner. For every visited entry mat[i][j], we compare the values of hor[i][j] and ver[i][j], and pick the smaller of two as we need a square. Let the smaller of two be ‘small’. After picking smaller of two, we check if both ver[][] and hor[][] for left and up edges respectively. If they have entries for the same, then we found a subsquare. Otherwise we try for small-1. 

Below is implementation of the above idea. 

4

Time complexity: O(N²).
Auxiliary Space: O(N²)

Optimized approach:

A more optimized solution would be to pre-compute the number of contiguous ‘X’ horizontally and vertically, in a matrix of pairs named dp. Now  for every entry of dp we have a pair (int, int) which denotes the maximum contiguous ‘X’ till that point, i.e.

• dp[i][j].first denotes contiguous ‘X’ taken horizontally till that point.
• dp[i][j].second denotes contiguous ‘X’ taken vertically till that point.

Now, a square can be formed with dp[i][j] as the bottom right corner, having sides atmost of length, min(dp[i][j].first, dp[i][j].second)

So, we make another matrix maxside, which will denote the maximum square side formed having the bottom right corner as arr[i][j]. We’ll try to get some intuition from the properties of a square, i.e. all the sides of the square are equal.

Let’s store maximum value that can be obtained, as val = min(dp[i][j].first, dp[i][j].second). From point (i, j), we traverse back horizontally by distance Val, and check if the minimum vertical contiguous ‘X’ till that point is equal to Val.

Similarly, we traverse back vertically by distance Val and check if the minimum horizontal contiguous ‘X’ till that point is equal to Val? Here we are making use of the fact that all sides of square are equal.

Input Matrix:

X  O  X  X  X  X

X  O  X  X  O  X

X  X  X  O  O  X

O  X  X  X  X  X

X  X  X  O  X  O

O  O  X  O  O  O

Value of matrix dp:

(1,1) (0,0) (1,1) (2,1) (3,1) (4,1)  

(1,2) (0,0) (1,2) (2,2) (0,0) (1,2)  

(1,3) (2,1) (3,3) (0,0) (0,0) (1,3)  

(0,0) (1,2) (2,4) (3,1) (4,1) (5,4)  

(1,1) (2,3) (3,5) (0,0) (1,2) (0,0)  

(0,0) (0,0) (1,6) (0,0) (0,0) (0,0) 

Below is the implementation of the above idea:

4

Time complexity: O(N²) 
Auxiliary space: O(N²)