20 lines C++ solution using dynamic programming


  • 18
    N

    class Solution {

    public:

    int maximalSquare(vector<vector<char>>& matrix) {
        if(matrix.size()==0) return 0;
        int maxSq=0;
        int nRow=matrix.size();
        int nCol=matrix[0].size();
        vector<vector<int>> dp(nRow+1,vector<int>(nCol+1,0));
        //dp[i][j] represents max square ending at position (i-1, j-1)
        for(int i=1;i<=nRow;++i){
            for(int j=1;j<=nCol;++j){
                if(matrix[i-1][j-1]=='1'){
                    dp[i][j]=min(min(dp[i-1][j-1],dp[i-1][j]),dp[i][j-1])+1;
                    maxSq=max(maxSq,dp[i][j]);
                }
            }
        }
        return maxSq*maxSq;
    }
    

    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.