Description#
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 <= 1001 <= grid[0].length <= 100grid[i][j] is 0 or 1
Solutions#
Solution 1: Prefix Sum + Enumeration#
We can use the prefix sum method to preprocess the number of consecutive 1s down and to the right of each position, denoted as down[i][j] and right[i][j].
Then we enumerate the side length $k$ of the square, starting from the largest side length. Then we enumerate the upper left corner position $(i, j)$ of the square. If it meets the condition, we can return $k^2$.
The time complexity is $O(m \times n \times \min(m, n))$, and the space complexity is $O(m \times n)$. Here, $m$ and $n$ are the number of rows and columns of the grid, respectively.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution:
def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
down = [[0] * n for _ in range(m)]
right = [[0] * n for _ in range(m)]
for i in range(m - 1, -1, -1):
for j in range(n - 1, -1, -1):
if grid[i][j]:
down[i][j] = down[i + 1][j] + 1 if i + 1 < m else 1
right[i][j] = right[i][j + 1] + 1 if j + 1 < n else 1
for k in range(min(m, n), 0, -1):
for i in range(m - k + 1):
for j in range(n - k + 1):
if (
down[i][j] >= k
and right[i][j] >= k
and right[i + k - 1][j] >= k
and down[i][j + k - 1] >= k
):
return k * k
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
| class Solution {
public int largest1BorderedSquare(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[][] down = new int[m][n];
int[][] right = new int[m][n];
for (int i = m - 1; i >= 0; --i) {
for (int j = n - 1; j >= 0; --j) {
if (grid[i][j] == 1) {
down[i][j] = i + 1 < m ? down[i + 1][j] + 1 : 1;
right[i][j] = j + 1 < n ? right[i][j + 1] + 1 : 1;
}
}
}
for (int k = Math.min(m, n); k > 0; --k) {
for (int i = 0; i <= m - k; ++i) {
for (int j = 0; j <= n - k; ++j) {
if (down[i][j] >= k && right[i][j] >= k && right[i + k - 1][j] >= k
&& down[i][j + k - 1] >= k) {
return k * k;
}
}
}
}
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
| class Solution {
public:
int largest1BorderedSquare(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
int down[m][n];
int right[m][n];
memset(down, 0, sizeof down);
memset(right, 0, sizeof right);
for (int i = m - 1; i >= 0; --i) {
for (int j = n - 1; j >= 0; --j) {
if (grid[i][j] == 1) {
down[i][j] = i + 1 < m ? down[i + 1][j] + 1 : 1;
right[i][j] = j + 1 < n ? right[i][j + 1] + 1 : 1;
}
}
}
for (int k = min(m, n); k > 0; --k) {
for (int i = 0; i <= m - k; ++i) {
for (int j = 0; j <= n - k; ++j) {
if (down[i][j] >= k && right[i][j] >= k && right[i + k - 1][j] >= k
&& down[i][j + k - 1] >= k) {
return k * k;
}
}
}
}
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
32
| func largest1BorderedSquare(grid [][]int) int {
m, n := len(grid), len(grid[0])
down := make([][]int, m)
right := make([][]int, m)
for i := range down {
down[i] = make([]int, n)
right[i] = make([]int, n)
}
for i := m - 1; i >= 0; i-- {
for j := n - 1; j >= 0; j-- {
if grid[i][j] == 1 {
down[i][j], right[i][j] = 1, 1
if i+1 < m {
down[i][j] += down[i+1][j]
}
if j+1 < n {
right[i][j] += right[i][j+1]
}
}
}
}
for k := min(m, n); k > 0; k-- {
for i := 0; i <= m-k; i++ {
for j := 0; j <= n-k; j++ {
if down[i][j] >= k && right[i][j] >= k && right[i+k-1][j] >= k && down[i][j+k-1] >= k {
return k * k
}
}
}
}
return 0
}
|
