Given a 2D binary matrix filled with0's and1's, find the largest square which diagonal is all1and others is0.

Notice

Only consider the main diagonal situation.

Have you met this question in a real interview?

Yes

Example

For example, given the following matrix:

1 0 1 0 0
1 0 0 1 0
1 1 0 0 1
1 0 0 1 0

Return9

public class Solution {

/\*\*

 \* @param matrix a matrix of 0 and 1

 \* @return an integer

 \*/

public int maxSquare2\(int\[\]\[\] matrix\) {

    // write your code here

    if \(matrix.length == 0 \|\| matrix\[0\].length == 0\) {

        return 0;

    }

    int n = matrix.length, m = matrix\[0\].length;

    int \[\]\[\] f = new int\[n\]\[m\];

    int \[\]\[\] u = new int\[n\]\[m\];

    int \[\]\[\] l = new int\[n\]\[m\];



    int len = 0;

    for \(int i = 0; i < n; ++i\) {

        for \(int j = 0; j < m; ++j\) {

            if \(matrix\[i\]\[j\] == 0\) {

                f\[i\]\[j\] = 0;

                u\[i\]\[j\] = l\[i\]\[j\] = 1;

                if \(i > 0\)

                    u\[i\]\[j\] = u\[i - 1\]\[j\] + 1;

                if \(j > 0\)

                    l\[i\]\[j\] = l\[i\]\[j - 1\] + 1;

            } else {

                if \(i == 0 \|\| j == 0\) {

                    f\[i\]\[j\] = 1;    

                } else {

                    f\[i\]\[j\] = Math.min\(f\[i - 1\]\[j - 1\], Math.min\(u\[i - 1\]\[j\], l\[i\]\[j - 1\]\)\) + 1;    

                }

                u\[i\]\[j\] = l\[i\]\[j\] = 0;

            }

            if \(f\[i\]\[j\] > len\) {

                len = f\[i\]\[j\];

            }

        }

    }

    return len \* len;

}

}