dp O(mn) time O(m) space
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
if (matrix.empty() || matrix[0].empty()) return 0;
int n = matrix.size(), m = matrix[0].size();
vector<int> dp(m + 1);
int res = 0, pre = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
int t = dp[j];
if (matrix[i - 1][j - 1] == '1') {
dp[j] = min(dp[j - 1], min(dp[j], pre)) + 1;
} else {
dp[j] = 0;
}
res = max(res, dp[j]);
pre = t;
}
}
return res * res;
}
};
|
dp + rolling array O(mn) time O(m) space
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
if (matrix.empty() || matrix[0].empty()) return 0;
int n = matrix.size(), m = matrix[0].size();
vector<vector<int>> dp(2, vector<int>(m + 1));
int res = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (matrix[i - 1][j - 1] == '1') {
dp[i % 2][j] = min(dp[i % 2][j - 1], min(dp[(i - 1) % 2][j], dp[(i - 1) % 2][j - 1])) + 1;
} else {
dp[i % 2][j] = 0;
}
res = max(res, dp[i % 2][j]);
}
}
return res * res;
}
};
|
dp O(mn) time O(mn) space
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
if (matrix.empty() || matrix[0].empty()) return 0;
int n = matrix.size(), m = matrix[0].size();
vector<vector<int>> dp(n + 1, vector<int>(m + 1));
int res = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (matrix[i - 1][j - 1] == '1') {
dp[i][j] = min({dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]}) + 1;
}
res = max(res, dp[i][j]);
}
}
return res * res;
}
};
|