# 1139. Largest 1-Bordered Square

Given a 2D `grid` of `0`s and `1`s, return the number of elements in the largest square subgrid that has all `1`s 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 <= 100`
• `1 <= grid[0].length <= 100`
• `grid[i][j]` is `0` or `1`

``````class Solution {
public:
int largest1BorderedSquare(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<vector<int>> left(m, vector<int>(n)), top(m, vector<int>(n));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 0) continue;
left[i][j] = j == 0 ? 1 : left[i][j - 1] + 1;
top[i][j] = i == 0 ? 1 : top[i - 1][j] + 1;
}
}
for (int len = min(m, n); len > 0; --len) {
for (int i = 0; i < m - len + 1; ++i) {
for (int j = 0; j < n - len + 1; ++j) {
if (top[i + len - 1][j] >= len && top[i + len - 1][j + len - 1] >= len && left[i][j + len - 1] >= len && left[i + len - 1][j + len - 1] >= len) return len * len;
}
}
}
return 0;
}
};
``````

``````class Solution {
public:
int largest1BorderedSquare(vector<vector<int>>& grid) {
int mx = 0, m = grid.size(), n = grid[0].size();
vector<vector<int>> left(m, vector<int>(n)), top(m, vector<int>(n));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 0) continue;
left[i][j] = j == 0 ? 1 : left[i][j - 1] + 1;
top[i][j] = i == 0 ? 1 : top[i - 1][j] + 1;
}
}
for (int i = m - 1; i >= 0; --i) {
for (int j = n - 1; j >= 0; --j) {
int small = min(left[i][j], top[i][j]);
while (small > mx) {
if (top[i][j - small + 1] >= small && left[i - small + 1][j] >= small) mx = small;
--small;
}
}
}
return mx * mx;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1139

https://leetcode.com/problems/largest-1-bordered-square/

https://leetcode.com/problems/largest-1-bordered-square/discuss/345233/JavaC%2B%2BPython-Straight-Forward

https://leetcode.com/problems/largest-1-bordered-square/discuss/345265/c%2B%2B-beats-100-(both-time-and-memory)-concise-with-algorithm-and-image

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation