Largest Subsquare Surrounded by X

Problem Overview

Only the border of the square must be X.

Intuition

Only the border of the square must be X. Precompute how far consecutive X runs stretch left and up into each cell, then for every bottom-right corner test shrinking side lengths until the left and top borders also qualify.

Algorithm

1Build hor[i][j] as consecutive X ending at (i, j) from the left.
2Build ver[i][j] as consecutive X ending at (i, j) from above.
3Scan cells from bottom-right toward top-left.
4Let size start at min(hor[i][j], ver[i][j]) and decrease while larger than the best answer.
5Accept size when ver[i][j-size+1] and hor[i-size+1][j] are both at least size.
6Return the best accepted side length.

Example Walkthrough

Input: matrix with an X-bordered 2x2 square and a larger open region

1. Prefix counts show solid bottom and right borders at a candidate corner.
2. Checking the opposite borders confirms side length 2.
3. Larger candidates fail a border check, so the answer stays 2.

Output: 2

Common Pitfalls

• This is not the filled maximal-square DP; interior cells may be O.
• Stop shrinking once size is not better than the current best.
• Reset consecutive counts when an O breaks a run.
• Indices j-size+1 and i-size+1 must stay inside the matrix, which follows from size <= hor/ver.

Largest Subsquare Surrounded by X.java

Java

// Approach: Precompute consecutive 'X' counts ending at each cell leftward
// (hor) and upward (ver). For every bottom-right corner, try side lengths
// from min(hor, ver) down to the best so far; a side-k square is valid when
// the left vertical and top horizontal borders also have length >= k.
// Complexity: O(n^3) time, O(n^2) space (standard for bordered squares).
class Solution {
    public int largestSubsquare(char[][] mat) {
        int n = mat.length;
        if (n == 0)
            return 0;
        int m = mat[0].length;

        int[][] hor = new int[n][m];
        int[][] ver = new int[n][m];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (mat[i][j] != 'X')
                    continue;
                hor[i][j] = (j > 0 ? hor[i][j - 1] : 0) + 1;
                ver[i][j] = (i > 0 ? ver[i - 1][j] : 0) + 1;
            }
        }

        int best = 0;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = m - 1; j >= 0; j--) {
                int size = Math.min(hor[i][j], ver[i][j]);
                while (size > best) {
                    // left vertical border and top horizontal border
                    if (ver[i][j - size + 1] >= size && hor[i - size + 1][j] >= size) {
                        best = size;
                        break;
                    }
                    size--;
                }
            }
        }
        return best;
    }
}

Was this solution helpful?