Maximal Square

Given a binary matrix, find out the largest size square sub-matrix with all 1's and return its area.

Input

• matrix: a binary matrix

Output

the area of the largest square in the input matrix

Examples

Example 1:

Input:

1matrix = 
2[[1, 0, 1, 0, 0],
3 [1, 0, 1, 1, 1],
4 [1, 1, 1, 1, 0],
5 [1, 0, 0, 1, 0]]
6

Output: 4

Explanation:

The largest square is of size 2x2 and area 4.

Try it yourself

Solution