221. Maximal Square
1. Description
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.
2. Example
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
3. Constraints
- m == matrix.length
- n == matrix[i].length
- 1 <= m, n <= 300
- matrix[i][j] is ‘0’ or ‘1’.
4. Solutions
Dynamic Programming
m = matrix.size(), n = matrix[0].size()
Time complexity: O(mn)
Space complexity: O(n)
class Solution {
public:
int maximalSquare(const vector<vector<char>> &matrix) {
// dp[i][j] means the largest square who bottom-right vertex is matrix[i][j]
vector<vector<int>> dp(2, vector<int>(matrix[0].size()));
int max_side = 0;
for (int i = 0; i < matrix.size(); ++i) {
dp[1][0] = matrix[i][0] == '1';
max_side = max(dp[1][0], max_side);
for (int j = 1; j < matrix[0].size(); ++j) {
dp[1][j] = matrix[i][j] == '1' ? 1 + min({dp[0][j - 1], dp[0][j], dp[1][j - 1]}) : 0;
max_side = max(dp[1][j], max_side);
}
dp[0] = dp[1];
}
return max_side * max_side;
}
};