Algorithm
Problem Name: 1139. Largest 1-Bordered Square
Problem Link: https://leetcode.com/problems/largest-1-bordered-square/
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
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;
};
Input
rid = [[1,1,1],[1,0,1],[1,1,1]]
Output
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
Input
rid = [[1,1,1],[1,0,1],[1,1,1]]
Output
9