Categories
Uncategorized

Largest 1-Bordered Square

class Solution {
    public int largest1BorderedSquare(int[][] grid) {
        int[][] h = new int[grid.length][grid[0].length];
        int[][] v = new int[grid.length][grid[0].length];
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 0) {
                    h[i][j] = 0;
                    v[i][j] = 0;
                } else {
                    h[i][j] = j > 0 ? h[i][j - 1] + 1 : 1;
                    v[i][j] = i > 0 ? v[i - 1][j] + 1 : 1;
                }
            }
        }
        int max = 0;
        for (int i = grid.length - 1; i >= 0; i--) {
            for (int j = grid[0].length - 1; j >= 0; j--) {
                int small = Math.min(v[i][j], h[i][j]);
                while (small > max) {
                    if (v[i][j + 1 - small] >= small && h[i + 1 - small][j] >= small) {
                        max = Math.max(max, small);
                    }
                    small--;
                }
            }
        }
        return max * max;
    }
}