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();
int max_length = 0;
vector<int> max_length_end_at(n, 0);
for (int i = 0; i < m; ++i) {
int prev = max_length_end_at[0];
max_length_end_at[0] = matrix[i][0] - '0';
max_length = max(max_length_end_at[0], max_length);
for (int j = 1; j < n; ++j) {
int temp = prev;
prev = max_length_end_at[j];
if (matrix[i][j] == '0') {
max_length_end_at[j] = 0;
} else {
max_length_end_at[j] =
min({temp, max_length_end_at[j], max_length_end_at[j - 1]}) + 1;
max_length = max(max_length_end_at[j], max_length);
}
}
}
return max_length * max_length;
}
};