Largest 1-Bordered Square

Given a 2D grid of 0s and 1s, return the number of elements in the largest square subgrid that has all 1s on its border, or 0 if such a subgrid doesn't exist in the grid.

Example 1:

Input: grid = [[1,1,1],[1,0,1],[1,1,1]]
Output: 9

Example 2:

Input: grid = [[1,1,0,0]]
Output: 1

Constraints:

• 1 <= grid.length <= 100

• 1 <= grid[0].length <= 100

• grid[i][j] is 0 or 1

Explaination:

Create auxillary horizontal and vertical arrays first For example :

image

Then starting from bottom right,for every i,j ; we find small=min (ver[i][j], hor[i][j]) (marked in orange) , then look at all distances in [1,small] vertically in hor array and horizontally in ver array. If values(shown in blue) are greater than small and if small is greater than curr result, then we update result

image

class Solution {
    public int largest1BorderedSquare(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] ver = new int[m][n];
        int[][] hor = new int[m][n];
        for (int j = 0; j < n; j++) {
            for (int i = 0; i < m; i++) {
                if (i == 0)
                    ver[i][j] = grid[i][j];
                else
                    ver[i][j] = grid[i][j] == 1 ? (ver[i - 1][j] + grid[i][j]) : 0;
                if (j == 0)
                    hor[i][j] = grid[i][j];
                else
                    hor[i][j] = grid[i][j] == 1 ? (hor[i][j - 1] + grid[i][j]) : 0;
            }
        }
        int max = 0;
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                int small = Math.min(hor[i][j], ver[i][j]); // choose smallest of horizontal and vertical value
                while (small > max) {
                    if (ver[i][j - small + 1] >= small && hor[i - small + 1][j] >= small)
                        // check if square exists with 'small' length
                        max = small;
                    small--;
                }
            }
        }
        return max * max;
    }
}