Problem Brief

Largest Square of 1's

A quality agent is responsible for inspecting samples of the finished products in the production line. Each sample contains defective and non-defective products represented by 1 and 0 respectively. The product samples are placed sequentially in a two-dimensional square matrix. The goal is to determine the size of the largest square of defective products in the two-dimensional square matrix.

Each line i of the n subsequent lines (where 0 ≤ i < n) contains n space-separated integers that describe samples[i].

Function Description

Complete the function largestSquareOfOnes in the editor.

largestSquareOfOnes has the following parameter:

int[][] samples: a two-dimensional array of integers representing the product samples

Returns

int: the size of the largest square of defective products

1Example 1

Input

samples = [[1,1,1,1,1],[1,1,1,0,0],[1,1,1,0,0],[1,1,1,0,0],[1,1,1,1,1]]

Output

Explanation

The first square of defective products is a sub-matrix 3 x 3 starting at (0,0) and ending at (3,3). The second square of defective products is also a sub-matrix 3 x 3 at (1,0), and ending at (4,3). The third square of defective products is also a sub-matrix 3 x 3 at (2,0), and ending at (5,3). The size of the largest square of defective products is 3.

2Example 2

Input

samples = [[1,1,1],[1,1,0],[1,0,1]]

Output

Explanation

The first square of defective products is a sub-matrix 2 x 2 starting at (0,0) and ending at (1,1). The other square of defective products are a sub-matrix 1 x 1 at (2,0), (0,2), and (2,2). The size of the largest square of defective products is 2.

3Example 3

Input

samples = [[0,1,1],[1,1,0],[1,0,1]]

Output

Explanation

All square of defective products are a sub-matrix 1 x 1 at (0,1), (0,2), (1,0), (1,1), (2,0), and (2,2). The size of the largest square of defective products is 1.

Constraints

Limits and guarantees your solution can rely on.

🥑🥑