Maximal Square

 

 

 

 Maximal Square

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

Example:

Input: 

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

 

 

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