221. Maximal Square | LeetCode Solution

 221. Maximal Square | LeetCode Solution

Given an m x n binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

 

Example 1:

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 4

Example 2:

Input: matrix = [["0","1"],["1","0"]]
Output: 1

Example 3:

Input: matrix = [["0"]]
Output: 0

 

Constraints:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 300
  • matrix[i][j] is '0' or '1'.


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

Post a Comment

0 Comments