1239. Largest 1-Bordered Square
My accepted Python solution to LeetCode problem 1239, Largest 1-Bordered Square, running in 105ms.
- Difficulty: Medium
- Python
- Runtime 105ms
- Memory 17.7MB
- Updated
Read the problem on LeetCode View on GitHub
The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.
Python
Accepted on LeetCode — runtime 105ms, memory 17.7MB, accepted 2026-01-02.
class Solution:
def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
# Precompute consecutive 1s going left and up
left = [[0] * n for _ in range(m)]
up = [[0] * n for _ in range(m)]
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
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
max_side = 0
for i in range(m):
for j in range(n):
# Try all possible square sizes
side = min(left[i][j], up[i][j])
while side > max_side:
# Check if we can form a square of this size
# Top-left corner would be at (i-side+1, j-side+1)
if up[i][j - side + 1] >= side and left[i - side + 1][j] >= side:
max_side = side
break
side -= 1
return max_side * max_side