All problems

Maximal Square

Medium · dynamic programming

You are given a rectangular board in which every cell holds the character "0" or the character "1".

Find the largest square made up entirely of "1" cells. The square must be solid: every cell inside it is "1", and its sides run along the rows and columns of the board.

Return the area of that square, that is, its side length multiplied by itself. If the board contains no "1" at all, return 0.

Examples

Example 1

Input: matrix = [["0", "1", "1", "0"], ["1", "1", "1", "1"], ["1", "1", "1", "1"], ["0", "1", "1", "0"]]

Output: 4

A 2 by 2 block of ones fits in many places, but no 3 by 3 block does.

Example 2

Input: matrix = [["1", "0"], ["0", "1"]]

Output: 1

The two ones touch only at a corner, so the biggest solid square is a single cell.

Example 3

Input: matrix = [["0", "0", "0"]]

Output: 0

There is no 1 anywhere.

Constraints

• 1 <= len(matrix), len(matrix[0]) <= 100
• Every row of matrix has the same length.
• Every cell of matrix is "0" or "1".