Funcia
Lv.2dpgrid

Largest Square Lawn

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
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

gridresult
["10100", "10111", "11111", "10010"]4
["01", "10"]1
["0"]0

Example 1 — The 2×22 \times 2 block covering rows 1–2 and columns 2–3 (0-based) is all grass; no 3×33 \times 3 block is.

Example 2 — Grass cells only touch diagonally, so 1×11 \times 1 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

  • 1≤H=1 \le H = grid.length ≤1,000\le 1{,}000
  • 1≤W=1 \le W = grid[i].length ≤1,000\le 1{,}000; all rows have the same length.
  • grid[i] consists of '0' and '1' only.

Expected complexity

Time
O(HW)
Space
O(W)

Examples

gridExpected
["10100","10111","11111","10010"]4
["01","10"]1
["0"]0

Hint

Hint

Growing a square from every cell costs up to O(min⁡(H,W)2)O(\min(H, W)^2) 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 O(HW)O(HW); the answer is the largest side squared.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251000 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4012verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.