Largest Unit Square

MEDIUM20 pts

You are given a two-dimensional grid of size m × n, where each cell contains either the character '0' or '1'. Your task is to discover the largest axis-aligned square region within the grid that is composed entirely of '1' cells.

Return the total area (i.e., the number of cells) of this largest all-ones square. If no such square exists (i.e., the grid contains only '0' cells), return 0.

A square region must:

Have equal width and height
Be aligned with the grid axes (no rotation)
Contain only '1' characters in every cell

The area of a square with side length s is s × s. For example, a square with side length 3 has an area of 9.

Example

Input

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

Output

4

Explanation

The largest square containing only '1's has a side length of 2 (located at rows 1-2, columns 2-3), giving an area of 2 × 2 = 4.

Example

Input

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

Output

1

Explanation

The largest square is a single cell with value '1'. There are two such cells, but each forms a square of side length 1, giving an area of 1 × 1 = 1.

Example

Input

matrix = [["0"]]

Output

0

Explanation

There are no '1' cells in the grid, so no valid square can be formed. The answer is 0.

Accepted0/0·0% Acceptance

Constraints

m == matrix.length
n == matrix[i].length
1 ≤ m, n ≤ 300
matrix[i][j] is either '0' or '1'

Code

Visualizer

Solutions

14px

Test Cases3

Results

Submissions

matrix =

[["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]

Return the total area (i.e., the number of cells) of this largest all-ones square. If no such square exists (i.e., the grid contains only '0' cells), return 0.

A square region must:

Have equal width and height
Be aligned with the grid axes (no rotation)
Contain only '1' characters in every cell

The area of a square with side length s is s × s. For example, a square with side length 3 has an area of 9.

Largest Unit Square

Hints

Largest Unit Square

Hints