Description

Suppose that there is a table (board) consisting of 1s and 0s. A space in the table is shaped as a 1 x 1 square. Write a function solution to find the largest square consisting of 1s in the table and return its size (The square must be parallel to the axis).

For example, assume that a table is given as follows.

1 2 3 4
0 1 1 1
1 1 1 1
1 1 1 1
0 0 1 0

Then, the largest square is as follows.

1 2 3 4
0 1 1 1
1 1 1 1
1 1 1 1
0 0 1 0

Since its size is 9, return 9.

Constraints
  • Table (board) is given as a 2-dimensional array.
  • Length of row of table (board) : natural number less than 1,000.
  • Length of column of table (board) : natural number less than 1,000.
  • Table (board) consists of only 1 and 0.

Examples
board answer
[[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]] 9
[[0,0,1,1],[1,1,1,1]] 4

Example #1
It is the same as the example in the problem statement.

Example #2
The largest square is as follows.
| 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 |
Since its size is 4, return 4.

Result Stop
Result of [Run] or [Submit] will be displayed here