Largest 1-Bordered Square — Solution in Python, Java & C++
Largest 1-Bordered Square solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Largest 1-Bordered Square is a medium coding problem on arrays, dynamic programming and matrix, asked in Google and Samsung interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming, Matrix
- Asked at: Google, Samsung
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a binary matrix grid of 0s and 1s. Find the largest square sub-grid whose border — its top row, bottom row, left column and right column — consists entirely of 1s. The cells strictly inside the border may hold anything.
Return the number of cells in that square (its side length squared), or 0 if the grid has no 1 at all.
Example 1
Input: grid = [[1,1,1,0],[1,0,1,1],[1,1,1,1]]
Output: 9
Explanation: The 3 × 3 square in the first three columns has a border of 1s; the 0 in its centre does not matter.
Example 2
Input: grid = [[0,1],[1,1]]
Output: 1
Explanation: The 2 × 2 square fails at its top-left corner, so the best is a single cell.
Example 3
Input: grid = [[0,0],[0,0]]
Output: 0
Constraints
1 <= grid.length <= 1001 <= grid[0].length <= 100grid[i][j] is 0 or 1
Hints for Largest 1-Bordered Square
Hint 1
A square of side
kwith bottom-right corner(i, j)needs four runs of at leastkones: leftwards and upwards from(i, j), upwards from(i, j-k+1)and leftwards from(i-k+1, j).Hint 2
Precompute, for every cell, how many consecutive 1s end there going left and going up.
Hint 3
For each cell as a bottom-right corner, try sides from
min(left, up)downwards and stop at the first side whose other two edges are long enough.
How to solve Largest 1-Bordered Square
With run-length tables left[i][j] (consecutive 1s ending at (i, j) along the row) and up[i][j] (along the column), each candidate square's border is verified in O(1).
Approach
- Scan the grid row by row. For a 1 at
(i, j)setleft[i][j] = left[i][j-1] + 1andup[i][j] = up[i-1][j] + 1(0 for a 0 cell). - Treat
(i, j)as the bottom-right corner. Forkfrommin(left[i][j], up[i][j])down tobest + 1: the bottom and right edges are guaranteed; check the left edgeup[i][j-k+1] >= kand the top edgeleft[i-k+1][j] >= k. - On the first
kthat passes, record it as the new best side and stop trying smaller sides at this corner. - Return
best * best.
Why it works
A square's border is exactly four straight runs of 1s of length k meeting at its corners, and each run is checked by one table lookup at the run's far end. Every square is tried at its bottom-right corner, so the maximum is found.
Complexity
- Time —
O(m · n · min(m, n)) - Space —
O(m · n)
Pitfalls
- The interior does not need to be 1s — only the border.
- Return the area (side squared), not the side length.
- A single 1 is already a valid 1 × 1 square.
Reference solution
Python
from typing import List
def largest1BorderedSquare(grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
left = [[0] * n for _ in range(m)]
up = [[0] * n for _ in range(m)]
best = 0
for i in range(m):
for j in range(n):
if grid[i][j] == 0:
continue
left[i][j] = (left[i][j - 1] if j > 0 else 0) + 1
up[i][j] = (up[i - 1][j] if i > 0 else 0) + 1
k = min(left[i][j], up[i][j])
while k > best:
if up[i][j - k + 1] >= k and left[i - k + 1][j] >= k:
best = k
break
k -= 1
return best * bestJava
public static int largest1BorderedSquare(int[][] grid) {
int m = grid.length, n = grid[0].length, best = 0;
int[][] left = new int[m][n], up = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 0) continue;
left[i][j] = (j > 0 ? left[i][j - 1] : 0) + 1;
up[i][j] = (i > 0 ? up[i - 1][j] : 0) + 1;
for (int k = Math.min(left[i][j], up[i][j]); k > best; k--) {
if (up[i][j - k + 1] >= k && left[i - k + 1][j] >= k) { best = k; break; }
}
}
}
return best * best;
}C++
int largest1BorderedSquare(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size(), best = 0;
vector<vector<int>> left(m, vector<int>(n, 0)), up(m, vector<int>(n, 0));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 0) continue;
left[i][j] = (j > 0 ? left[i][j - 1] : 0) + 1;
up[i][j] = (i > 0 ? up[i - 1][j] : 0) + 1;
for (int k = min(left[i][j], up[i][j]); k > best; k--) {
if (up[i][j - k + 1] >= k && left[i - k + 1][j] >= k) { best = k; break; }
}
}
}
return best * best;
}JavaScript
var largest1BorderedSquare = function(grid) {
var m = grid.length, n = grid[0].length, best = 0;
var left = [], up = [];
for (var r = 0; r < m; r++) { left.push(new Array(n).fill(0)); up.push(new Array(n).fill(0)); }
for (var i = 0; i < m; i++) {
for (var j = 0; j < n; j++) {
if (grid[i][j] === 0) continue;
left[i][j] = (j > 0 ? left[i][j - 1] : 0) + 1;
up[i][j] = (i > 0 ? up[i - 1][j] : 0) + 1;
for (var k = Math.min(left[i][j], up[i][j]); k > best; k--) {
if (up[i][j - k + 1] >= k && left[i - k + 1][j] >= k) { best = k; break; }
}
}
}
return best * best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming