# [leetcode] Maximal Square

### Maximal Square

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

For example, given the following matrix:

```1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
```

Return 4.

Credits:
Special thanks to @Freezen for adding this problem and creating all test cases.

Dynamic programming, dp[i][j] stores the maximum side length of square whose bottom-right coordinate is (i, j)

dp[i][0] = matrix[i][0] – ‘0’

dp[0][i] = matrix[0][i] – ‘0’

dp[i][j] = 0 if matrix[i][j] == 0

dp[i][j] = 1 + min(dp[i – 1][j], dp[i – 1][j – 1], dp[i][j – 1])

```//dp stores the maximum side length of square whose bottom-right coordinate is (i, j)
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
int ans = 0;
if(matrix.size() == 0) return 0;
int dp[matrix.size()][matrix[0].size()];
for(int i = 0; i < matrix.size(); i++){
if(matrix[i][0] == '0'){
dp[i][0] = 0;
}
else{
dp[i][0] = 1;
ans = 1;
}
}
for(int j = 0; j < matrix[0].size(); j++){
if(matrix[0][j] == '0'){
dp[0][j] = 0;
}
else{
dp[0][j] = 1;
ans = 1;
}
}
for(int i = 1; i < matrix.size(); i++){
for(int j = 1; j < matrix[0].size(); j++){
if(matrix[i][j] == '0'){
dp[i][j] = 0;
}
else{
dp[i][j] = 1 + min(dp[i - 1][j - 1], min(dp[i][j - 1], dp[i - 1][j]));
}
ans = max(ans, dp[i][j]);
}
}
return ans * ans;
}

};```

This site uses Akismet to reduce spam. Learn how your comment data is processed.