class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int n = matrix.size();
        int m = matrix[0].size();
        int ans = 0;
        vector<vector<int>> temp;
        for(int i=0; i<n; i++) {
            vector<int> t(m,0);
            temp.push_back(t);
        }
        for(int i=0; i<n; i++) {
            if(matrix[i][0]=='1') {
                temp[i][0]=1;
                ans=1;
            } else {
                temp[i][0]=0;
            }
        }
        for(int i=0; i<m; i++) {
            if(matrix[0][i]=='1') {
                temp[0][i]=1;
                ans=1;
            } else {
                temp[0][i]=0;
            }
        }
        for(int i=1; i<n; i++) {
            for(int j=1; j<m; j++) {
                if(matrix[i][j]=='0') {
                    temp[i][j]=0;
                } else {
                    int x = min(min(temp[i][j-1], temp[i-1][j-1]), temp[i-1][j]);
                    temp[i][j]=1+x;
                    if(ans < temp[i][j]) {
                        ans = temp[i][j];
                    }
                }
            }
        }
        return ans*ans;
    }
};