In this guide, you will get 1139. Largest 1-Bordered Square LeetCode Solution with the best time and space complexity. The solution to Largest -Bordered Square problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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
Complexity Analysis
Time Complexity:
Space Complexity:
1139. Largest 1-Bordered Square LeetCode Solution in C++
class Solution {
public:
int largest1BorderedSquare(vector<vector<int>>& grid) {
const int m = grid.size();
const int n = grid[0].size();
// leftOnes[i][j] := consecutive 1s in the left of grid[i][j]
vector<vector<int>> leftOnes(m, vector<int>(n));
// topOnes[i][j] := consecutive 1s in the top of grid[i][j]
vector<vector<int>> topOnes(m, vector<int>(n));
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (grid[i][j] == 1) {
leftOnes[i][j] = j == 0 ? 1 : 1 + leftOnes[i][j - 1];
topOnes[i][j] = i == 0 ? 1 : 1 + topOnes[i - 1][j];
}
for (int sz = min(m, n); sz > 0; --sz)
for (int i = 0; i + sz - 1 < m; ++i)
for (int j = 0; j + sz - 1 < n; ++j) {
const int x = i + sz - 1;
const int y = j + sz - 1;
// If grid[i..x][j..y] has all 1s on its border.
if (min(leftOnes[i][y], leftOnes[x][y]) >= sz &&
min(topOnes[x][j], topOnes[x][y]) >= sz)
return sz * sz;
}
return 0;
}
}; /* code provided by PROGIEZ */
1139. Largest 1-Bordered Square LeetCode Solution in Java
class Solution {
public int largest1BorderedSquare(int[][] grid) {
final int m = grid.length;
final int n = grid[0].length;
// leftOnes[i][j] := consecutive 1s in the left of grid[i][j]
int[][] leftOnes = new int[m][n];
// topOnes[i][j] := consecutive 1s in the top of grid[i][j]
int[][] topOnes = new int[m][n];
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (grid[i][j] == 1) {
leftOnes[i][j] = j == 0 ? 1 : 1 + leftOnes[i][j - 1];
topOnes[i][j] = i == 0 ? 1 : 1 + topOnes[i - 1][j];
}
for (int sz = Math.min(m, n); sz > 0; --sz)
for (int i = 0; i + sz - 1 < m; ++i)
for (int j = 0; j + sz - 1 < n; ++j) {
final int x = i + sz - 1;
final int y = j + sz - 1;
// If grid[i..x][j..y] has all 1s on its border.
if (Math.min(leftOnes[i][y], leftOnes[x][y]) >= sz &&
Math.min(topOnes[x][j], topOnes[x][y]) >= sz)
return sz * sz;
}
return 0;
}
}; // code provided by PROGIEZ
1139. Largest 1-Bordered Square LeetCode Solution in Python
class Solution:
def largest1BorderedSquare(self, grid: list[list[int]]) -> int:
m = len(grid)
n = len(grid[0])
# leftOnes[i][j] := consecutive 1s in the left of grid[i][j]
leftOnes = [[0] * n for _ in range(m)]
# topOnes[i][j] := consecutive 1s in the top of grid[i][j]
topOnes = [[0] * n for _ in range(m)]
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
leftOnes[i][j] = 1 if j == 0 else 1 + leftOnes[i][j - 1]
topOnes[i][j] = 1 if i == 0 else 1 + topOnes[i - 1][j]
for sz in range(min(m, n), 0, -1):
for i in range(m - sz + 1):
for j in range(n - sz + 1):
x = i + sz - 1
y = j + sz - 1
# If grid[i..x][j..y] has all 1s on its border.
if min(
leftOnes[i][y],
leftOnes[x][y],
topOnes[x][j],
topOnes[x][y]) >= sz:
return sz * sz
return 0 # code by PROGIEZ
