Given a 2D binary matrix filled with 0's and 1's, find the largest square containing all 1's and return its area.

Have you met this question in a real interview?

Yes

Example

For example, given the following matrix:

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

Return4.

class Solution {

public:

/\*\*

 \* @param matrix: a matrix of 0 and 1

 \* @return: an integer

 \*/

int maxSquare\(vector<vector<int> > &matrix\) {

    // write your code here

    if \(matrix.empty\(\) \|\| matrix\[0\].empty\(\)\) {

        return 0;

    }

    int len = 0, n = matrix.size\(\), m = matrix\[0\].size\(\);

    vector<vector<int>> f\(2, vector<int>\(m, 0\)\);



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

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

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

                f\[i%2\]\[j\] = matrix\[i\]\[j\];

                len = max\(len, f\[i%2\]\[j\]\);

                continue;

            }



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

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

                continue;

            }



            f\[i%2\]\[j\] = min\(min\(f\[\(i-1\)%2\]\[j-1\], f\[i%2\]\[j-1\]\), f\[\(i-1\)%2\]\[j\]\) + 1;

            len =  max\(len, f\[i%2\]\[j\]\);

        }

    }



    return len\*len;

}

};