Largest 1-Bordered Square
MedPrompt
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: 9Example 2:
Input: grid = [[1,1,0,0]]
Output: 1
Constraints:
1 <= grid.length <= 1001 <= grid[0].length <= 100grid[i][j]is0or1
Approaches
2 approaches with complexity analysis and trade-offs.
This straightforward approach involves iterating through every possible top-left corner and every possible size for a square subgrid. For each potential square, it explicitly checks if all four borders consist of '1's.
Algorithm
- Initialize
maxLen = 0. - Iterate through each cell
(r, c)of the grid, treating it as a potential top-left corner of a square. - For each
(r, c), iterate through all possible side lengthslenfrom1up to the maximum possible from that corner (min(rows - r, cols - c)). - For each potential square defined by
(r, c)andlen, check if its border is composed entirely of1s.- This involves checking four sides: the top row from
ctoc + len - 1at rowr, the bottom row atr + len - 1, the left column fromrtor + len - 1at columnc, and the right column atc + len - 1.
- This involves checking four sides: the top row from
- If all four sides consist of
1s, updatemaxLen = max(maxLen, len). - After checking all possibilities, return
maxLen * maxLen.
Walkthrough
The algorithm uses three nested loops. The outer two loops select a cell (r, c) as the potential top-left corner of a square. The third loop iterates through possible side lengths len, starting from 1. For each combination of (r, c, len), a helper function is called to verify the border. This helper function iterates along the top, bottom, left, and right edges of the potential square. If it finds any '0', it invalidates the square. If the square is valid, we update our record of the maximum side length found so far. This process is repeated for all possible squares in the grid.
class Solution { public int largest1BorderedSquare(int[][] grid) { int rows = grid.length; int cols = grid[0].length; int maxLen = 0; for (int r = 0; r < rows; r++) { for (int c = 0; c < cols; c++) { for (int len = 1; r + len <= rows && c + len <= cols; len++) { if (isBordered(grid, r, c, len)) { maxLen = Math.max(maxLen, len); } } } } return maxLen * maxLen; } private boolean isBordered(int[][] grid, int r, int c, int len) { // Check top and bottom borders for (int j = c; j < c + len; j++) { if (grid[r][j] == 0 || grid[r + len - 1][j] == 0) { return false; } } // Check left and right borders for (int i = r; i < r + len; i++) { if (grid[i][c] == 0 || grid[i][c + len - 1] == 0) { return false; } } return true; }}Complexity
Time
O(m * n * min(m, n) * min(m, n)). For an N x N grid, this is O(N^4). There are O(N^3) possible squares, and verifying each takes O(N) time.
Space
O(1), as no extra space proportional to the input size is used.
Trade-offs
Pros
Simple to understand and implement.
Uses constant extra space (
O(1)).
Cons
Extremely inefficient due to multiple nested loops and redundant checks.
The time complexity of
O(N^4)makes it infeasible for the given constraints, likely leading to a 'Time Limit Exceeded' error.
This optimized approach uses dynamic programming to avoid redundant calculations. It pre-computes the lengths of consecutive '1's extending horizontally to the left and vertically upwards from each cell. This information allows for a much faster verification of whether a potential square has a 1-border.
Algorithm
- Create two DP tables,
hor[m][n]andver[m][n], to store lengths of consecutive1s. - Populate
horandverin a single pass (O(m*n)):- For each cell
(i, j): - If
grid[i][j] == 1:hor[i][j] = (j > 0) ? hor[i][j-1] + 1 : 1;ver[i][j] = (i > 0) ? ver[i-1][j] + 1 : 1;
- For each cell
- Initialize
maxLen = 0. - Iterate through the grid from bottom-right to top-left (
ifromm-1to0,jfromn-1to0). - For each cell
(i, j), determine the maximum possible side length for a square ending at this corner:side = min(hor[i][j], ver[i][j]). - Check for a valid square by shrinking
sidedownwards:while (side > maxLen):- A square of size
sideneeds its top and left borders to be long enough. - Check if
ver[i][j - side + 1] >= side(left border) andhor[i - side + 1][j] >= side(top border). - If both are true, a valid square is found. Update
maxLen = sideand break the innerwhileloop. - Otherwise, decrement
sideand check again.
- A square of size
- Return
maxLen * maxLen.
Walkthrough
The core idea is to build two DP tables, hor and ver. hor[i][j] stores the number of consecutive '1's to the left of grid[i][j] (inclusive), and ver[i][j] stores the number of consecutive '1's above grid[i][j] (inclusive). After populating these tables, we iterate through the grid, considering each cell (i, j) as the potential bottom-right corner of a square. The maximum possible side length side for a square ending at (i, j) is min(hor[i][j], ver[i][j]). We then check if a square of this side is valid by using our DP tables to instantly look up the lengths of the corresponding top and left borders. We start with the largest possible side for (i, j) and decrease it until we find a valid square or the size becomes too small. This avoids the costly re-scanning of the brute-force method.
class Solution { public int largest1BorderedSquare(int[][] grid) { int m = grid.length; int n = grid[0].length; int[][] hor = new int[m][n]; int[][] ver = new int[m][n]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == 1) { hor[i][j] = (j > 0) ? hor[i][j - 1] + 1 : 1; ver[i][j] = (i > 0) ? ver[i - 1][j] + 1 : 1; } } } int maxLen = 0; for (int i = m - 1; i >= 0; i--) { for (int j = n - 1; j >= 0; j--) { int side = Math.min(hor[i][j], ver[i][j]); while (side > maxLen) { // Check if the top and left borders are valid if (ver[i][j - side + 1] >= side && hor[i - side + 1][j] >= side) { maxLen = side; break; // Found the largest square for this corner } side--; } } } return maxLen * maxLen; }}Complexity
Time
O(m * n * min(m, n)). The pre-computation is O(m*n). The main loop is O(m*n), and inside it, the while loop can run up to min(m,n) times. For an N x N grid, this is O(N^3).
Space
O(m * n) to store the two DP tables, `hor` and `ver`.
Trade-offs
Pros
Significantly more efficient than the brute-force approach.
Fast enough to pass the given constraints.
The use of DP tables effectively caches intermediate results, avoiding re-computation.
Cons
Requires extra space proportional to the grid size for the DP tables.
Solutions
Solution
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; }}class Solution {public: int largest1BorderedSquare(vector<vector<int>> &grid) { int m = grid.size(), n = grid[0].size(); int down[m][n]; int right[m][n]; memset(down, 0, sizeof down); memset(right, 0, sizeof right); 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 = 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; }};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 0Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.