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.
classSolution {
public:int largest1BorderedSquare(std::vector<std::vector<int>>& mat) {
int n = mat.size();
int m = mat[0].size();
int ans =0;
for (int r =0; r < n; ++r) {
for (int c =0; c < m; ++c) {
for (int sz =1; r + sz <= n && c + sz <= m; ++sz) {
bool ok = true;
int r2 = r + sz -1;
int c2 = c + sz -1;
for (int j = c; j <= c2 && ok; ++j) {
if (!mat[r][j] ||!mat[r2][j]) ok = false;
}
for (int i = r; i <= r2 && ok; ++i) {
if (!mat[i][c] ||!mat[i][c2]) ok = false;
}
if (ok) ans = std::max(ans, sz * sz);
}
}
}
return ans;
}
};
classSolution {
publicintlargest1BorderedSquare(int[][] mat) {
int n = mat.length, m = mat[0].length;
int ans = 0;
for (int r = 0; r < n; ++r) {
for (int c = 0; c < m; ++c) {
for (int sz = 1; r + sz <= n && c + sz <= m; ++sz) {
boolean ok =true;
int r2 = r + sz - 1, c2 = c + sz - 1;
for (int j = c; j <= c2 && ok; ++j) {
if (mat[r][j]== 0 || mat[r2][j]== 0) ok =false;
}
for (int i = r; i <= r2 && ok; ++i) {
if (mat[i][c]== 0 || mat[i][c2]== 0) ok =false;
}
if (ok) ans = Math.max(ans, sz * sz);
}
}
}
return ans;
}
}
classSolution:
deflargest1BorderedSquare(self, mat: list[list[int]]) -> int:
n = len(mat)
m = len(mat[0])
ans =0for r in range(n):
for c in range(m):
sz =1while r + sz <= n and c + sz <= m:
ok =True r2 = r + sz -1 c2 = c + sz -1for j in range(c, c2 +1):
if mat[r][j] ==0or mat[r2][j] ==0:
ok =Falsebreakfor i in range(r, r2 +1) and ok:
if mat[i][c] ==0or mat[i][c2] ==0:
ok =Falsebreakif ok:
ans = max(ans, sz * sz)
sz +=1return ans
To find the largest 1-bordered square, for each cell, we need to know how many consecutive 1’s are to its left and above. This allows us to quickly check if a square of a given size ending at (i, j) has all 1’s on its border.
classSolution {
public:int largest1BorderedSquare(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size(), ans =0;
vector<vector<int>> left(m, vector<int>(n)), up(m, vector<int>(n));
for (int i =0; i < m; ++i)
for (int j =0; j < n; ++j) {
if (grid[i][j]) {
left[i][j] = (j ? left[i][j-1] :0) +1;
up[i][j] = (i ? up[i-1][j] :0) +1;
}
}
for (int i =0; i < m; ++i)
for (int j =0; j < n; ++j) {
int k = min(left[i][j], up[i][j]);
while (k >0) {
if (left[i-k+1][j] >= k && up[i][j-k+1] >= k) {
ans = max(ans, k*k);
break;
}
--k;
}
}
return ans;
}
};
classSolution {
publicintlargest1BorderedSquare(int[][] grid) {
int m = grid.length, n = grid[0].length, ans = 0;
int[][] left =newint[m][n], up =newint[m][n];
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (grid[i][j]== 1) {
left[i][j]= (j > 0 ? left[i][j-1] : 0) + 1;
up[i][j]= (i > 0 ? up[i-1][j] : 0) + 1;
}
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j) {
int k = Math.min(left[i][j], up[i][j]);
while (k > 0) {
if (left[i-k+1][j]>= k && up[i][j-k+1]>= k) {
ans = Math.max(ans, k*k);
break;
}
k--;
}
}
return ans;
}
}
classSolution {
funlargest1BorderedSquare(grid: Array<IntArray>): Int {
val m = grid.size
val n = grid[0].size
val left = Array(m) { IntArray(n) }
val up = Array(m) { IntArray(n) }
var ans = 0for (i in0 until m)
for (j in0 until n)
if (grid[i][j] ==1) {
left[i][j] = if (j > 0) left[i][j-1] + 1else1 up[i][j] = if (i > 0) up[i-1][j] + 1else1 }
for (i in0 until m)
for (j in0 until n) {
var k = minOf(left[i][j], up[i][j])
while (k > 0) {
if (left[i-k+1][j] >= k && up[i][j-k+1] >= k) {
ans = maxOf(ans, k*k)
break }
k-- }
}
return ans
}
}
classSolution:
deflargest1BorderedSquare(self, grid: list[list[int]]) -> int:
m, n = len(grid), len(grid[0])
left = [[0]*n for _ in range(m)]
up = [[0]*n for _ in range(m)]
for i in range(m):
for j in range(n):
if grid[i][j]:
left[i][j] = (left[i][j-1] if j else0) +1 up[i][j] = (up[i-1][j] if i else0) +1 ans =0for i in range(m):
for j in range(n):
k = min(left[i][j], up[i][j])
while k >0:
if left[i-k+1][j] >= k and up[i][j-k+1] >= k:
ans = max(ans, k*k)
break k -=1return ans
impl Solution {
pubfnlargest1_bordered_square(grid: Vec<Vec<i32>>) -> i32 {
let m = grid.len();
let n = grid[0].len();
letmut left =vec![vec![0; n]; m];
letmut up =vec![vec![0; n]; m];
for i in0..m {
for j in0..n {
if grid[i][j] ==1 {
left[i][j] =if j >0 { left[i][j-1] +1 } else { 1 };
up[i][j] =if i >0 { up[i-1][j] +1 } else { 1 };
}
}
}
letmut ans =0;
for i in0..m {
for j in0..n {
letmut k = left[i][j].min(up[i][j]);
while k >0 {
if left[i-k+1][j] >= k && up[i][j-k+1] >= k {
ans = ans.max(k*k);
break;
}
k -=1;
}
}
}
ans
}
}