## Algorithm

Problem Name: 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`

## Code Examples

### #1 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const largest1BorderedSquare = function(grid) {
let A = grid;
let m = A.length,
n = A[0].length;
let max = 0;
const hori = Array.from(Array(m)).map(() => Array(n).fill(0));
const ver = Array.from(Array(m)).map(() => Array(n).fill(0));
for (let i = 0; i  <  m; ++i) {
for (let j = 0; j  <  n; ++j) {
if (A[i][j] > 0) {
hori[i][j] = j > 0 ? hori[i][j - 1] + 1 : 1;
ver[i][j] = i > 0 ? ver[i - 1][j] + 1 : 1;
}
}
}
for (let i = m - 1; i >= 0; i--) {
for (let j = n - 1; j >= 0; j--) {
let small = Math.min(hori[i][j], ver[i][j]);
while (small > max) {
if (ver[i][j - small + 1] >= small && hori[i - small + 1][j] >= small) {
max = small;
break
}
small--;
}
}
}
return max * max;
};
``````
Copy The Code &

Input

cmd
rid = [[1,1,1],[1,0,1],[1,1,1]]

Output

cmd
9

### #2 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def largest1BorderedSquare(self, A: List[List[int]]) -> int:
m, n = len(A), len(A[0])
res = 0
top, left = [a[:] for a in A], [a[:] for a in A]
for i in range(m):
for j in range(n):
if A[i][j]:
if i: top[i][j] = top[i - 1][j] + 1
if j: left[i][j] = left[i][j - 1] + 1
for r in range(min(m, n), 0, -1):
for i in range(m - r + 1):
for j in range(n - r + 1):
if min(top[i + r - 1][j], top[i + r - 1][j + r - 1], left[i]
[j + r - 1], left[i + r - 1][j + r - 1]) >= r:
return r * r
return 0
``````
Copy The Code &

Input

cmd
rid = [[1,1,1],[1,0,1],[1,1,1]]

Output

cmd
9