Largest 1-Bordered Square LeetCode solution in Java

1
class Solution {
2
  public int largest1BorderedSquare(int[][] grid) {
3
    int m = grid.length;
4
    int n = grid[0].length;
5
    // rows[r][c] is the length of the line ended at [r,c] on row r
6
    int[][] rows = new int[m][n];
7
    // the length of the line ended at [r,c] on colume c
8
    int[][] cols = new int[m][n];
9
    int res = 0;
10
    for (int r = 0; r < m; r++) {
11
      for (int c = 0; c < n; c++) {
12
        if (grid[r][c] == 0) {
13
          rows[r][c] = 0;
14
          cols[r][c] = 0;
15
        } else {
16
          rows[r][c] = c == 0 ? 1 : rows[r][c - 1] + 1;
17
          cols[r][c] = r == 0 ? 1 : cols[r - 1][c] + 1;
18
          if (res >= rows[r][c] || res >= cols[r][c]) {
19
            continue;
20
          }
21
          res = Math.max(res, getD(rows, cols, r, c));
22
        }
23
      }
24
    }
25
    return res * res;
26
  }
27

28
  // get the dimension of the largest square which bottom-right point is [row,col]
29
  private int getD(int[][] rows, int[][] cols, int row, int col) {
30
    int len = Math.min(rows[row][col], cols[row][col]);
31
    for (int i = len - 1; i >= 0; i--) {
32
      if (rows[row - i][col] > i && cols[row][col - i] > i) {
33
        return i + 1;
34
      }
35
    }
36
    return 1;
37
  }
38
}