Largest 1-Bordered Square
Largest 1-Bordered Square is a medium dynamic programming problem solved with the squares pattern.
The best approach, optimal (run-length prefix tables), runs in O(m · n · min(m, n)) time and O(m · n) space.
Below are 2 approaches in Java, from brute force border check up.
Problem
Return the area of the largest square whose border is made entirely of 1s. The inside of the square can be anything. Return 0 if there is none.
Examples
Example 1
- Input
grid = [[1,1,1],[1,0,1],[1,1,1]]- Output
9- Why
- The 3 × 3 border is all 1s; the inside does not matter.
Example 2
- Input
grid = [[1,1,0,0]]- Output
1
Constraints
1 <= m, n <= 100; values 0 or 1.- Return the area.
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.
| Approach | Time | Space |
|---|---|---|
| Brute force border check | O(m · n · min(m, n)²) | O(1) |
| Optimal (run-length prefix tables) | O(m · n · min(m, n)) | O(m · n) |
1Brute force border check
O(m · n · min(m, n)²)O(1)For each top-left corner and size, walk the four sides to confirm they are all 1s.
- For every (i, j, size), check 4 · size cells.
class Solution {
public int largest1BorderedSquare(int[][] grid) {
int m = grid.length, n = grid[0].length, best = 0;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
for (int s = 1; i + s <= m && j + s <= n; s++) {
boolean ok = true;
for (int k = 0; k < s && ok; k++)
if (grid[i][j + k] == 0 || grid[i + s - 1][j + k] == 0
|| grid[i + k][j] == 0 || grid[i + k][j + s - 1] == 0) ok = false;
if (ok) best = Math.max(best, s);
}
return best * best;
}
}2Optimal (run-length prefix tables)
O(m · n · min(m, n))O(m · n)hor[i][j] = consecutive 1s ending at (i, j) from the left; ver[i][j] = from above. For bottom-right corner (i, j), try sizes s from min(hor, ver) down. The square works if the top edge (hor at row i - s + 1) and the left edge (ver at column j - s + 1) both reach at least s.
- Fill hor and ver.
- For each (i, j), for s = min(hor, ver) down to best + 1: if hor[i - s + 1][j] >= s and ver[i][j - s + 1] >= s, best = s; break.
class Solution {
public int largest1BorderedSquare(int[][] grid) {
int m = grid.length, n = grid[0].length, best = 0;
int[][] hor = new int[m][n], 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] : 0) + 1;
ver[i][j] = (i > 0 ? ver[i - 1][j] : 0) + 1;
}
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
for (int s = Math.min(hor[i][j], ver[i][j]); s > best; s--)
if (hor[i - s + 1][j] >= s && ver[i][j - s + 1] >= s) { best = s; break; }
return best * best;
}
}Edge cases to test
- No 1s (0)
- The centre is 0 but the border is complete
Hints
Hint 1
Precompute, for every cell, how many consecutive 1s end there going left (hor) and going up (ver). Then any border check is O(1).
FAQ
What is the best time complexity for Largest 1-Bordered Square?
Optimal (run-length prefix tables) runs in O(m · n · min(m, n)) time and O(m · n) extra space.
Which pattern does Largest 1-Bordered Square use?
It is a dynamic programming problem that uses the squares pattern. Other problems with the same pattern: Maximal Square, Count Square Submatrices with All Ones.
Is there a brute force solution for Largest 1-Bordered Square?
Yes. Brute force border check takes O(m · n · min(m, n)²) time and O(1) space. For each top-left corner and size, walk the four sides to confirm they are all 1s.
Which edge cases should I test for Largest 1-Bordered Square?
No 1s (0); The centre is 0 but the border is complete.