Maximal Square
Real-world version: Largest Intact Mosaic SquareThe statement here is our own: the same inputs, outputs and technique.
A mosaic panel is surveyed tile by tile into matrix. Each entry is the one-character string "1" when that tile is intact or "0" when it is cracked.
A restorer wants to cut out the largest square block of tiles that contains no cracked tile. The block must be aligned with the grid and every tile inside it must be intact.
Return the number of tiles such a largest square block covers, or 0 when every tile is cracked.
Examples
Example 1
- Input
- matrix = [["1","0","1","1"],["1","1","1","1"],["0","1","1","1"]]
- Output
- 4
The tiles in rows 1 and 2 across columns 2 and 3 are all intact, giving a 2 by 2 block that covers 4 tiles. No 3 by 3 block is free of cracks.
Example 2
- Input
- matrix = [["0","1"],["1","1"]]
- Output
- 1
Three tiles are intact but they do not form a 2 by 2 block, so the best square is a single tile covering 1 tile.
Example 3
- Input
- matrix = [["0","0"],["0","0"]]
- Output
- 0
Every tile is cracked, so no square block can be cut at all.
Constraints
- m == matrix.length
- n == matrix[r].length
- 1 <= m, n <= 300
- matrix[r][c] is "0" or "1".
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def maximal_square(matrix: list[list[str]]) -> int:public int maximalSquare(char[][] matrix)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 9 test cases: 9 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's