# [Question] Largest Sub-square With Edges Filled

### Question

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(n3).

### 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;
}
``````