1139. Largest 1-Bordered Square

Link

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

Solution

• Count the number of consecutive 1s on the top and on the left.

• From length of edge l = min(m,n) to l = 1, check if the 1-bordered square exist.

Time O(N^3) Space O(N^2)

    public int largest1BorderedSquare(int[][] grid) {
        int M = grid.length;
        int N = grid[0].length;
        int[][] top = new int[M][N];
        int[][] left = new int[M][N];
        
        for(int i = 0; i < M; i++){
            for(int j = 0; j < N; j++){
                if(grid[i][j] == 1){
                    top[i][j] = j > 0 ? top[i][j-1] + 1 : 1;
                    left[i][j] = i > 0 ? left[i-1][j] + 1 : 1;
                }
                
            }
        }
        
        for(int l = Math.min(M, N); l > 0; l--){
            for(int i = 0; i < M-l+1; i++){
                for(int j = 0; j < N-l+1; j++){  
                    if(top[i][j+l-1] >= l && top[i+l-1][j+l-1] >= l
                      && left[i+l-1][j] >= l && left[i+l-1][j+l-1] >= l){
                        return l*l;
                    }
                    
                }
                
            }
            
        }
        return 0;
    }