716. Largest Solid Square
A farmer's field is described by grid, a rectangle of one-character cells: "1" is fertile soil and "0" is rock. The farmer wants to mark out a square plot, with sides parallel to the field edges, that contains only fertile cells.
Cells are only compared by their character, rows all have the same length, and a single fertile cell already forms a plot of side 1. Different square positions may tie; only the size matters.
Return the area (number of cells) of the largest such square, or 0 if the field has no fertile cell at all.
Aim for time O(rows * cols) and extra space O(cols).
Example 1
- Input:
- grid = [["1","0","1","1","1"],["1","1","1","1","1"],["0","1","1","1","1"],["1","1","1","1","0"]]
- Output:
- 9
- Explanation:
A 3 x 3 block of fertile cells starts at row 1, column 1, and no 4 x 4 block exists, so the area is 9.
Example 2
- Input:
- grid = [["1","1","1"],["1","1","1"]]
- Output:
- 4
- Explanation:
The tallest square that fits in 2 rows is 2 x 2, so the area is 4.
Constraints
1 ≤ rows, cols ≤ 300
grid[r][c] is either "0" or "1"
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(rows * cols)
- Space
- O(cols)