Largest 1-Bordered Square

LeetCode Q 1139 - 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

Solution:

hor[i][j]: means the length of the longest line of '1‘s starting from (i, j) and going left.
ver[i][j]: means the length of the longest line of '1's starting from (i, j) and going up.

Code:

public int largest1BorderedSquare(int[][] grid) {
  int R = grid.length, C = grid[0].length;
  int[][] hor = new int[R][C], ver = new int[R][C]; 

  for (int r = 0; r < R; r++) {
    for (int c = 0; c < C; c++) {
      if (grid[r][c] == 1) {
      	hor[r][c] = c == 0 ? 1 : hor[r][c - 1] + 1;
        ver[r][c] = r == 0 ? 1 : ver[r - 1][c] + 1;
      }
    }
  }

  int max = 0;
  for (int r = R - 1; r >=0 ; r--) {
    for (int c = C - 1; c >= 0; c--) {
      if (grid[r][c] == 0) continue;
      int edge = Math.min(hor[r][c], ver[r][c]);
      while (edge > max) {
        if (hor[r-edge+1][c] >= edge && ver[r][c-edge+1] >= edge) {
          max = edge;
          break;
        }
        edge--;
      }
    }
  }

  return max * max;
}