Maximal Square Problem
Description
LeetCode Problem 221.
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:
1
2
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:
1
2
Input: matrix = [["0","1"],["1","0"]]
Output: 1
Example 3:
1
2
Input: matrix = [["0"]]
Output: 0
Constraints:
- m == matrix.length
- n == matrix[i].length
- 1 <= m, n <= 300
- matrix[i][j] is ‘0’ or ‘1’.
Sample C++ Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
int maxSquare = 0;
int m = matrix.size();
if (m == 0) return 0;
int n = matrix[0].size();
int l;
int maxL = 0;
vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
for (int i = 1; i <= m; i ++) {
for (int j = 1; j <= n; j ++) {
if (matrix[i-1][j-1] == '1') {
l = min(dp[i-1][j], dp[i][j-1]);
if (matrix[i-l-1][j-l-1] == '1')
dp[i][j] = l + 1;
else
dp[i][j] = l;
maxL = max(maxL, dp[i][j]);
}
//cout << dp[i][j] << " ";
}
cout << endl;
}
return maxL*maxL;
}
};