Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1139.html
1139. Largest 1-Bordered Square (Medium)
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]is0or1
Related Topics:
Dynamic Programming
Solution 1. Matrix Prefix Sum
// OJ: https://leetcode.com/problems/largest-1-bordered-square/
// Time: O(MN * min(M, N))
// Space: O(MN)
class Solution {
inline int getCount(vector<vector<int>> &cnt, int a, int b, int c, int d) {
return cnt[c + 1][d + 1] - cnt[a][d + 1] - cnt[c + 1][b] + cnt[a][b];
}
public:
int largest1BorderedSquare(vector<vector<int>>& G) {
int M = G.size(), N = G[0].size(), ans = 0;
vector<vector<int>> cnt(M + 1, vector<int>(N + 1));
for (int i = 0; i < M; ++i) {
int sum = 0;
for (int j = 0; j < N; ++j) {
sum += G[i][j];
cnt[i + 1][j + 1] = cnt[i][j + 1] + sum;
}
}
for (int a = 0; a < M; ++a) {
for (int b = 0; b < N; ++b) {
if (G[a][b] == 0) continue;
ans = max(ans, 1);
for (int len = 2; a + len - 1 < M && b + len - 1 < N; ++len) {
int c = a + len - 1, d = b + len - 1;
if (getCount(cnt, a, b, c, d) - getCount(cnt, a + 1, b + 1, c - 1, d - 1) != (c - a) * 2 + (d - b) * 2) continue;
ans = max(ans, len * len);
}
}
}
return ans;
}
};
Solution 2. Prefix Sum per Row and Column
// OJ: https://leetcode.com/problems/largest-1-bordered-square/
// Time: O(MN * min(M, N))
// Space: O(MN)
class Solution {
public:
int largest1BorderedSquare(vector<vector<int>>& G) {
int M = G.size(), N = G[0].size(), ans = 0;
vector<vector<int>> row(M, vector<int>(N + 1)), col(M + 1, vector<int>(N));
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) row[i][j + 1] = row[i][j] + G[i][j];
}
for (int j = 0; j < N; ++j) {
for (int i = 0; i < M; ++i) col[i + 1][j] = col[i][j] + G[i][j];
}
for (int a = 0; a < M; ++a) {
for (int b = 0; b < N; ++b) {
for (int len = 1; a + len - 1 < M && b + len - 1 < N; ++len) {
int c = a + len - 1, d = b + len - 1;
if (G[a][d] == 0 || G[c][b] == 0) break;
if (row[c][d + 1] - row[c][b] != len || col[c + 1][d] - col[a][d] != len) continue;
ans = max(ans, len * len);
}
}
}
return ans;
}
};
Optimizations based on the above solution:
- The row and column indexes
aandbcan ends atM - ansandN - ans. Greater row/column indexes are impossible to get better answer. - Instead of scanning from
len = 1every time, start fromlen = {previous longest valid length} + 1.
// OJ: https://leetcode.com/problems/largest-1-bordered-square/
// Time: O(MN * min(M, N))
// Space: O(MN)
class Solution {
public:
int largest1BorderedSquare(vector<vector<int>>& G) {
int M = G.size(), N = G[0].size(), ans = 0;
vector<vector<int>> row(M, vector<int>(N + 1)), col(M + 1, vector<int>(N));
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) row[i][j + 1] = row[i][j] + G[i][j];
}
for (int j = 0; j < N; ++j) {
for (int i = 0; i < M; ++i) col[i + 1][j] = col[i][j] + G[i][j];
}
for (int a = 0; a < M - ans; ++a) {
for (int b = 0; b < N - ans; ++b) {
for (int len = ans + 1; a + len - 1 < M && b + len - 1 < N; ++len) {
int c = a + len - 1, d = b + len - 1;
if (row[a][d + 1] - row[a][b] != len || col[c + 1][b] - col[a][b] != len) break;
if (row[c][d + 1] - row[c][b] != len || col[c + 1][d] - col[a][d] != len) continue;
ans = max(ans, len);
}
}
}
return ans * ans;
}
};
-
class Solution { public int largest1BorderedSquare(int[][] grid) { int maxSide = 0; int rows = grid.length, columns = grid[0].length; for (int i = 0; i < rows; i++) { for (int j = 0; j < columns; j++) { if (grid[i][j] == 1) { maxSide = Math.max(maxSide, 1); int curMaxSide = Math.min(rows - i, columns - j); for (int k = 1; k < curMaxSide; k++) { if (grid[i][j + k] == 0 || grid[i + k][j] == 0) break; if (grid[i + k][j + k] == 0) continue; boolean flag = true; for (int m = 1; m < k; m++) { if (grid[i + k][j + m] == 0 || grid[i + m][j + k] == 0) { flag = false; break; } } if (flag) maxSide = Math.max(maxSide, k + 1); } } } } return maxSide * maxSide; } } ############ 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; } } -
// OJ: https://leetcode.com/problems/largest-1-bordered-square/ // Time: O(MN * min(M, N)) // Space: O(MN) class Solution { inline int getCount(vector<vector<int>> &cnt, int a, int b, int c, int d) { return cnt[c + 1][d + 1] - cnt[a][d + 1] - cnt[c + 1][b] + cnt[a][b]; } public: int largest1BorderedSquare(vector<vector<int>>& G) { int M = G.size(), N = G[0].size(), ans = 0; vector<vector<int>> cnt(M + 1, vector<int>(N + 1)); for (int i = 0; i < M; ++i) { int sum = 0; for (int j = 0; j < N; ++j) { sum += G[i][j]; cnt[i + 1][j + 1] = cnt[i][j + 1] + sum; } } for (int a = 0; a < M; ++a) { for (int b = 0; b < N; ++b) { if (G[a][b] == 0) continue; ans = max(ans, 1); for (int len = 2; a + len - 1 < M && b + len - 1 < N; ++len) { int c = a + len - 1, d = b + len - 1; if (getCount(cnt, a, b, c, d) - getCount(cnt, a + 1, b + 1, c - 1, d - 1) != (c - a) * 2 + (d - b) * 2) continue; ans = max(ans, len * len); } } } return ans; } }; -
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 ############ # 1139. Largest 1-Bordered Square # https://leetcode.com/problems/largest-1-bordered-square/ class Solution: def largest1BorderedSquare(self, grid: List[List[int]]) -> int: res = 0 rows, cols = len(grid), len(grid[0]) def check(x, y): return 0 <= x < rows and 0 <= y < cols def dfs(i, j, size): res = 1 isValid = canContinue = True mx, my = i + size, j + size if not check(mx, my): return res for dy in range(j, my + 1): if check(i, dy) and check(mx, dy) and grid[i][dy] == 0 or grid[mx][dy] == 0: isValid = False if grid[i][dy] == 0: canContinue = False for dx in range(i, mx + 1): if check(dx, j) and check(dx, my) and grid[dx][j] == 0 or grid[dx][my] == 0: isValid = False if grid[dx][j] == 0: canContinue = False if isValid: res = max(res, (size + 1) * (size + 1)) if canContinue and check(i + size + 1, j + size + 1): res = max(res, dfs(i, j, size + 1)) return res for i in range(rows): for j in range(cols): if grid[i][j] == 1: res = max(res, dfs(i, j, 0)) return res -
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 } func min(a, b int) int { if a < b { return a } return b }