# 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.
Example:
Input:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Output: 4
# Solution
Approach 1: DP.
# Code (Python)
Approach 1:
def maximalSquare(self, matrix: List[List[str]]) -> int:
# DP. Use 2 rows to keep track of the max square for each cell (or better -- just 1 row, but keep the previous value in a temp variable)
# sides[i][j] = min(sides[i-1][j], sides[i][j-2], sides[i-1][j-1]) + 1
if not matrix or not matrix[0]:
return 0
sides = [0 if element == '0' else 1 for element in matrix[0]]
max_side = max(sides)
for row_num in range(1, len(matrix)):
prev = sides[0]
sides[0] = 0 if matrix[row_num][0] == '0' else 1
for col_num in range(1, len(matrix[0])):
temp_prev = sides[col_num]
if matrix[row_num][col_num] == '1':
sides[col_num] = 1 + min(
prev,
sides[col_num],
sides[col_num-1])
else:
sides[col_num] = 0
prev = temp_prev
max_side = max(max(sides), max_side)
return max_side * max_side
# Code (C++)
Approach 1:
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
int m = matrix.size();
if (m == 0) return 0;
int n = matrix[0].size();
if (n == 0) return 0;
/*
int len[m+1][n+1] = {0};
for (int i = 0; i <= m; ++i) len[i][0] = 0;
for (int j = 0; j <= n; ++j) len[0][j] = 0;
*/
int len[n+1] = {0};
int prev = 0;
int maxLen = 0;
for (int i = 1; i <= m; ++i)
{
for (int j = 1; j <= n; ++j)
{
int temp = len[j]; // need to be here.
if (matrix[i-1][j-1] == '1')
{
/*
len[i][j] = 1 + std::min(
std::min(len[i-1][j], len[i][j-1]),
len[i-1][j-1]);
maxLen = std::max(maxLen, len[i][j]);
*/
len[j] = 1 + std::min(std::min(len[j], prev), len[j-1]);
maxLen = std::max(maxLen, len[j]);
}
else
{
len[j] = 0; // need to assign 0 to overwrite the previous value.
}
prev = temp; // need to be here.
}
}
return maxLen * maxLen;
}
};