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;
}
};
0 Comments
If you have any doubts/suggestion/any query or want to improve this article, you can comment down below and let me know. Will reply to you soon.