Maximal Square_2.cpp

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int m = matrix.size(), n = m? matrix[0].size(): 0, maxSquare = 0;
        vector<int> dp(n, 0);
        for(int i = 0; i < m; ++i)
        {
            int cache = 0;
            for(int j = 0; j < n; ++j)
            {
                int temp = dp[j];
                if(matrix[i][j] == '1')
                {
                    if(!i || !j)
                        dp[j] = 1;
                    else
                    {
                        if(dp[j] > 0 && dp[j - 1] > 0 && cache > 0)
                            dp[j] = min(min(dp[j], dp[j - 1]), cache) + 1;
                        else
                            dp[j] = 1;
                    }
                    maxSquare = max(maxSquare, dp[j] * dp[j]);
                }
                else
                    dp[j] = 0;
                cache = temp;
            }     
        }
        return maxSquare;
    }
};