Largest Solid Square Plot
Medium2-D Dynamic Programming
Problem
A land survey is stored as a binary grid land: 1 marks buildable ground and 0 marks rock. A developer wants one square plot, aligned with the grid, made entirely of buildable cells.
Return the area (number of cells) of the largest such square, or 0 if there is no buildable cell.
Example 1
- Input:
- land = [[1, 0, 1, 1, 1], [1, 1, 1, 1, 1], [0, 1, 1, 1, 1], [1, 0, 1, 1, 0]]
- Output:
- 9
Rows 0–2, columns 2–4 form a 3 × 3 block of 1s.
Example 2
- Input:
- land = [[0, 0], [0, 0]]
- Output:
- 0
Constraints
- 1 ≤ land.length, land[0].length ≤ 300
- land[r][c] is 0 or 1
Hint
Show the first hint
Instead of testing every square, ask: what is the biggest all-1 square whose bottom-right corner is (r, c)?
Walkthrough
How to approach it
01Clarify before coding
- Return the area or the side? The area, so square the side at the end.
- Must the square be axis-aligned? Yes, rows and columns of the grid.
- Is the grid always rectangular and non-empty? Yes.
02Brute force
For every cell as top-left corner, grow the square while the new row and column are all 1s.
Cost: O(m · n · min(m, n)²) in the worst case (an all-1 grid); around 10^9–10^10 for 300 × 300.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.