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;

        

    }

};