Maximal Square

matrix holds 0s and 1s. Return the area of the largest square that contains only 1s.

For [[1, 0, 1, 0, 0], [1, 0, 1, 1, 1], [1, 1, 1, 1, 1], [1, 0, 0, 1, 0]] the answer is 4.

The starter code checks every possible square cell by cell. It is correct but too slow for big matrices.

Examples

Example 1

Input:

maximal_square([[1, 0, 1, 0, 0], [1, 0, 1, 1, 1], [1, 1, 1, 1, 1], [1, 0, 0, 1, 0]])

Output:

4

Example 2

Input:

maximal_square([[0, 1], [1, 0]])

Output:

1

Constraints

• 0 <= rows, cols <= 500
• Every cell is 0 or 1.