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; } }
Categories