Skip to content

1139. Largest 1-Bordered Square 👍

  • Time:
  • Space: 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
 public:
  int largest1BorderedSquare(vector<vector<int>>& grid) {
    const int m = grid.size();
    const int n = grid[0].size();

    // leftOnes[i][j] := consecutive 1s in the left of grid[i][j]
    vector<vector<int>> leftOnes(m, vector<int>(n));
    // topOnes[i][j] := consecutive 1s in the top of grid[i][j]
    vector<vector<int>> topOnes(m, vector<int>(n));

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        if (grid[i][j] == 1) {
          leftOnes[i][j] = j == 0 ? 1 : 1 + leftOnes[i][j - 1];
          topOnes[i][j] = i == 0 ? 1 : 1 + topOnes[i - 1][j];
        }

    for (int sz = min(m, n); sz > 0; --sz)
      for (int i = 0; i + sz - 1 < m; ++i)
        for (int j = 0; j + sz - 1 < n; ++j) {
          const int x = i + sz - 1;
          const int y = j + sz - 1;
          // If grid[i..x][j..y] has all 1s on its border.
          if (min(leftOnes[i][y], leftOnes[x][y]) >= sz &&
              min(topOnes[x][j], topOnes[x][y]) >= sz)
            return sz * sz;
        }

    return 0;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
  public int largest1BorderedSquare(int[][] grid) {
    final int m = grid.length;
    final int n = grid[0].length;

    // leftOnes[i][j] := consecutive 1s in the left of grid[i][j]
    int[][] leftOnes = new int[m][n];
    // topOnes[i][j] := consecutive 1s in the top of grid[i][j]
    int[][] topOnes = new int[m][n];

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        if (grid[i][j] == 1) {
          leftOnes[i][j] = j == 0 ? 1 : 1 + leftOnes[i][j - 1];
          topOnes[i][j] = i == 0 ? 1 : 1 + topOnes[i - 1][j];
        }

    for (int sz = Math.min(m, n); sz > 0; --sz)
      for (int i = 0; i + sz - 1 < m; ++i)
        for (int j = 0; j + sz - 1 < n; ++j) {
          final int x = i + sz - 1;
          final int y = j + sz - 1;
          // If grid[i..x][j..y] has all 1s on its border.
          if (Math.min(leftOnes[i][y], leftOnes[x][y]) >= sz &&
              Math.min(topOnes[x][j], topOnes[x][y]) >= sz)
            return sz * sz;
        }

    return 0;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
  def largest1BorderedSquare(self, grid: list[list[int]]) -> int:
    m = len(grid)
    n = len(grid[0])

    # leftOnes[i][j] := consecutive 1s in the left of grid[i][j]
    leftOnes = [[0] * n for _ in range(m)]
    # topOnes[i][j] := consecutive 1s in the top of grid[i][j]
    topOnes = [[0] * n for _ in range(m)]

    for i in range(m):
      for j in range(n):
        if grid[i][j] == 1:
          leftOnes[i][j] = 1 if j == 0 else 1 + leftOnes[i][j - 1]
          topOnes[i][j] = 1 if i == 0 else 1 + topOnes[i - 1][j]

    for sz in range(min(m, n), 0, -1):
      for i in range(m - sz + 1):
        for j in range(n - sz + 1):
          x = i + sz - 1
          y = j + sz - 1
          # If grid[i..x][j..y] has all 1s on its border.
          if min(
                  leftOnes[i][y],
                  leftOnes[x][y],
                  topOnes[x][j],
                  topOnes[x][y]) >= sz:
            return sz * sz

    return 0