# 221. Maximal Square

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

For example, given the following matrix:

``````1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
``````

Return 4.

Thoughts:

1. different approach from maximal rectangle problems (84 and 85 )since it is a square (current state value only depends on top, left and top-left corner
2. f[i][j] number of maximal square from matrix[0, ...i -1][0,...j-1] so far

3. initial state: f[i] = f[j] = 0

4. recursive state : f[i][j] = min(f[i-1][j], f[i][j-1], f[i-1][j-1]) for (1<= i <= matrix.size(); 1<=j<=matrix.size()).

5. further optimization

Code Time Complexity O(row * col), Space Complexity O(row * col)

``````class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
if(matrix.empty()) return 0;
int m = matrix.size(), n = matrix.size();
vector<vector<int>> f(m + 1, vector<int>(n + 1, 0));
int ans = 0;
for(int i = 1; i <= m; i ++){
for(int j = 1; j <=n; j ++){
if(matrix[i-1][j-1] == '1'){
f[i][j] = min(f[i-1][j], min(f[i-1][j-1], f[i][j-1])) + 1;
ans = max(ans, f[i][j]);
}
}
}

return ans * ans;
}
};
``````

Code (Optimization): with Space Complexity O(row) or O(col)

``````int maximalSquare(vector<vector<char>>& matrix) {
if (matrix.empty()) return 0;
int m = matrix.size(), n = matrix.size();
vector<int> dp(m + 1, 0); // 0 padding on the top
int maxsize = 0, pre = 0;
for (int j = 0; j < n; j++) {
for (int i = 1; i <= m; i++) {
int temp = dp[i];
if (matrix[i - 1][j] == '1') {
dp[i] = min(dp[i], min(dp[i - 1], pre)) + 1; //dp[i]: dp[i][j-1], dp[i-1]: dp[i-1][j]
maxsize = max(maxsize, dp[i]);
}
else dp[i] = 0;
pre = temp; // serve as dp[i-1][j-1] for the next iteration
}
}
return maxsize * maxsize;
}
``````

Special Thanks to jianchao.li.fighter's solution