Largest Square Lawn
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 0
A park office keeps a grid map grid of the park: grid[i] is the i-th row as a string, where '1' marks a grass cell and
'0' marks bare ground.
For a picnic festival they want the largest axis-aligned square made only of grass cells. Return its area (number of
cells), or 0 if there is no grass at all.
Examples
| grid | result |
|---|---|
["10100", "10111", "11111", "10010"] | 4 |
["01", "10"] | 1 |
["0"] | 0 |
Example 1 — The block covering rows 1–2 and columns 2–3 (0-based) is all grass; no block is.
Example 2 — Grass cells only touch diagonally, so is the best.
Example 3 — There is no grass.
Efficiency
This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.
Function signature
solution(grid: string[]) → int
Constraints
-
grid.length -
grid[i].length; all rows have the same length. grid[i]consists of'0'and'1'only.
Expected complexity
- Time
- O(HW)
- Space
- O(W)
Examples
| grid | Expected |
|---|---|
["10100","10111","11111","10010"] | 4 |
["01","10"] | 1 |
["0"] | 0 |
Hint
Hint
Growing a square from every cell costs up to per cell on dense grass and times out. Let side[i][j] be
the side of the largest grass square whose bottom-right corner is (i, j): for a grass cell
side[i][j] = 1 + min(side[i-1][j], side[i][j-1], side[i-1][j-1]), and 0 otherwise. One pass is ; the answer is
the largest side squared.
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | estimated |
| C++ (GCC, gnu++23) | 200 ms | derived |
| Python 3.13 | 1000 ms | derived |
| Java 25 | 1000 ms | derived |
| Kotlin 2.4 (JVM) | 1400 ms | estimated |
| C# 14 (.NET 10) | 1400 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 3 | inputs and outputs |
| correctness | 40 | 12 | verdict only |
| performance | 60 | 4 | verdict only |