Maximal Square

Problem

You are given a binary matrix of '0' and '1' characters. Find the largest square sub-block consisting entirely of '1' and return its area.

• 1 <= rows, cols <= 300
• Each cell is the character '0' or '1'.

Examples

• matrix = [["1","1","0","1","1"],["1","1","1","1","0"],["0","1","1","1","1"],["1","1","1","0","0"]] → 4. A 2x2 block of ones sits in rows 0-1, columns 0-1.
• matrix = [["1","0"],["0","1"]] → 1. No two adjacent ones form a square larger than a single cell.
• matrix = [["0"]] → 0. No ones at all.

Hints

1. Think about squares by their bottom-right corner. If a square of side k ends at a cell, what must be true of the cells above, to the left, and diagonally up-left?
2. Three overlapping squares of side k-1 ending at those three neighbours, plus a one in the current cell, guarantee a square of side k.
3. dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) when the cell is a one, else 0. Answer is max(dp)².