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.front().size()
Time complexity: O(mn)
Space complexity: O(n)
class Solution {
public:
int maximalSquare(const vector<vector<char>> &matrix) {
const int m = matrix.size(), n = matrix.front().size();
vector<int> max_length(n, 0);
int max_size = 0;
for (int i = 0; i < m; ++i) {
int prev = max_length[0];
max_length[0] = static_cast<int>(matrix[i][0] == '1');
max_size = max(max_size, max_length[0] * max_length[0]);
for (int j = 1; j < n; ++j) {
int backup = max_length[j];
if (matrix[i][j] == '0') {
max_length[j] = 0;
} else {
max_length[j] = min(max_length[j], min(prev, max_length[j - 1])) + 1;
max_size = max(max_size, max_length[j] * max_length[j]);
}
prev = backup;
}
}
return max_size;
}
};