Maximal Square

Standard Bar Dynamic Programming · DP on Squares O(m*n) · O(n)

The Solar Panel String Survey

A rooftop survey maps a grid of mounting points as either reinforced (1) or not (0). The installation crew wants to deploy one big square solar string whose anchors occupy a perfect block of reinforced points only. Survey software must report the area of the largest such square block anywhere on the roof.

Input: An m x n binary matrix matrix of '0' and '1' characters.

Output: Return the area of the largest square submatrix consisting entirely of 1s.

Constraints

1 <= m, n <= 300
matrix[i][j] is '0' or '1'

Examples

Example 1

Input: {"matrix":[["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]}
Output: 4
A 2x2 block of 1s sits in the middle-right region; area 4.

Example 2

Input: {"matrix":[["0","1"],["1","0"]]}
Output: 1
No 2x2 block exists, but single reinforced points give area 1.

Solve this in your browser →

Also on LeetCode ↗