Question

link

Given a matrix where every element is either ‘O’ or ‘X’, find the largest sub-square surrounded by ‘X’. (meaning that the 4 edges are filled with ‘X’)

Example Input:

 {'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 sub-squre.

Example Input:

 {'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

Solution

Read a very similar question - [Question] Maximum Square Sub-matrix With All 1s

Typical DP question. Now the solution is to build 2 arrays to cache info. One horizontally and one, vertical.

create two auxiliary arrays hor[N][N] and ver[N][N].

hor[i][j] is the number of horizontal continuous ‘X’ characters till mat[i][j] in mat[][].

ver[i][j] is the number of vertical continuous ‘X’ characters till mat[i][j] in mat[][]. 

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

After we got these, start from the bottom-right corner row by row up… For every mat[i][j], we compare hor[i][j] with ver[i][j] and pick the smaller one.

All we need to do next, is to check the other 2 edges. This solution is O(n^3).

Code

C++ code provided by G4G:

int findSubSquare(int mat[][N])
{
    int max = 1; // Initialize result

    // Initialize the left-top value in hor[][] and ver[][]
    int hor[N][N], ver[N][N];
    hor[0][0] = ver[0][0] = (mat[0][0] == 'X');

    // Fill values in hor[][] and ver[][]
    for (int i=0; i<N; i++)
    {
        for (int j=0; j<N; j++)
        {
            if (mat[i][j] == 'O')
                ver[i][j] = hor[i][j] = 0;
            else
            {
                hor[i][j] = (j==0)? 1: hor[i][j-1] + 1;
                ver[i][j] = (i==0)? 1: ver[i-1][j] + 1;
            }
        }
    }

    // Start from the rightmost-bottommost corner element and find
    // the largest ssubsquare with the help of hor[][] and ver[][]
    for (int i = N-1; i>=1; i--)
    {
        for (int j = N-1; j>=1; j--)
        {
            // Find smaller of values in hor[][] and ver[][]
            // A Square can only be made by taking smaller
            // value
            int small = getMin(hor[i][j], ver[i][j]);

            // At this point, we are sure that there is a right
            // vertical line and bottom horizontal line of length
            // at least 'small'.

            // We found a bigger square if following conditions
            // are met:
            // 1)If side of square is greater than max.
            // 2)There is a left vertical line of length >= 'small'
            // 3)There is a top horizontal line of length >= 'small'
            while (small > max)
            {
                if (ver[i][j-small+1] >= small &&
                    hor[i-small+1][j] >= small)
                {
                    max = small;
                }
                small--;
            }
        }
    }
    return max;
}