Square of ones

Determine the largest square of 1s in a binary matrix (a binary matrix only contains 0 and 1), return the length of the largest square.

Assumptions

• The given matrix is not null and guaranteed to be of size N * N, N >= 0

Examples

{ {0, 0, 0, 0},

{1, 1, 1, 1},

{0, 1, 1, 1},

{1, 0, 1, 1}}

the largest square of 1s has length of 2

High Level:

Dp approach.

M[i][j] represents the max side length of square with i,j as lower right corner.

For top edge and left edge:

1 if current spot is 1, else 0

For rest of matrix:

M[i][j] = minimum between its three neighboring tiles + 1

For a tile to be  2 side length, every neighbor must be 1 length
1 1
1 x  side length = 2

1 0
1 x side length = 1

For a tile to be 3 side length, every neighbor must be 2 length
1 1 1
1 1 1
1 1 x side length = 3

1 1 0
1 1 1
1 1 x side length = 2

1 1 1
1 1 1
0 1 x side length = 2

0 1 1
1 1 1
1 1 x side length = 2

Each N length square is made up of four N - 1 length squares with a overlapping center.