grid is a list of rows of equal length, each a string of '0' and '1' characters. Find the biggest square block of cells that holds only '1's: its sides run along the rows and columns, and every cell inside it must be a '1'.
Write maximal_square(grid: list[str]) -> int that returns the area of that square (side × side), or 0 if the grid has no '1' at all.
Examples:
maximal_square(["01101",
"11111",
"01111",
"11110"]) # 9
The 3 × 3 square covers rows 1 to 3 and columns 1 to 3. No 4 × 4 square fits: the grid has only 4 rows, and every 4 × 4 window includes a '0'.
maximal_square(["0110",
"1111",
"1111",
"0110"]) # 4 twelve 1s, but every 3 × 3 window has a 0 corner
maximal_square(["000", "000"]) # 0
Constraints: 1 <= rows, columns <= 300.
⭐ Bonus: speed tests on 300 × 300 grids earn a star in O(rows · columns). Growing a square from every cell and rechecking its cells is far too slow when most of the grid is '1'.
Show hint
if a square of side s ends at a cell (as its bottom-right corner), what must be true of the squares ending at the cells above, to the left and diagonally up-left?