##### 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 <= 100
• 1 <= grid[0].length <= 100
• grid[i][j] is 0 or 1

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 a and b can ends at M - ans and N - ans. Greater row/column indexes are impossible to get better answer.
• Instead of scanning from len = 1 every time, start from len = {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
}