• Time:O(mn)
• Space:O(mn)

## C++

``````class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
const int m = matrix.size();
const int n = matrix[0].size();
vector<vector<int>> dp(m, vector<int>(n));
int maxLength = 0;

for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j) {
if (i == 0 || j == 0 || matrix[i][j] == '0')
dp[i][j] = matrix[i][j] == '1' ? 1 : 0;
else
dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;
maxLength = max(maxLength, dp[i][j]);
}

return maxLength * maxLength;
}
};
``````

## JAVA

``````class Solution {
public int maximalSquare(char[][] matrix) {
final int m = matrix.length;
final int n = matrix[0].length;
int[][] dp = new int[m][n];
int maxLength = 0;

for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j) {
if (i == 0 || j == 0 || matrix[i][j] == '0')
dp[i][j] = matrix[i][j] == '1' ? 1 : 0;
else
dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
maxLength = Math.max(maxLength, dp[i][j]);
}

return maxLength * maxLength;
}
}
``````

## Python

``````class Solution:
def maximalSquare(self, matrix: List[List[str]]) -> int:
m = len(matrix)
n = len(matrix[0])
dp = [[0] * n for _ in range(m)]
maxLength = 0

for i in range(m):
for j in range(n):
if i == 0 or j == 0 or matrix[i][j] == '0':
dp[i][j] = 1 if matrix[i][j] == '1' else 0
else:
dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1]
[j], dp[i][j - 1]) + 1
maxLength = max(maxLength, dp[i][j])

return maxLength * maxLength
``````

• Time:O(mn)
• Space:O(n)

## C++

``````class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
const int m = matrix.size();
const int n = matrix[0].size();
vector<int> dp(n);
int maxLength = 0;
int prev = 0;  // dp[i - 1][j - 1]

for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j) {
const int cache = dp[j];
if (i == 0 || j == 0 || matrix[i][j] == '0')
dp[j] = matrix[i][j] == '1' ? 1 : 0;
else
dp[j] = min({prev, dp[j], dp[j - 1]}) + 1;
maxLength = max(maxLength, dp[j]);
prev = cache;
}

return maxLength * maxLength;
}
};
``````

## JAVA

``````class Solution {
public int maximalSquare(char[][] matrix) {
final int m = matrix.length;
final int n = matrix[0].length;
int[] dp = new int[n];
int maxLength = 0;
int prev = 0; // dp[i - 1][j - 1]

for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j) {
final int cache = dp[j];
if (i == 0 || j == 0 || matrix[i][j] == '0')
dp[j] = matrix[i][j] == '1' ? 1 : 0;
else
dp[j] = Math.min(prev, Math.min(dp[j], dp[j - 1])) + 1;
maxLength = Math.max(maxLength, dp[j]);
prev = cache;
}

return maxLength * maxLength;
}
}
``````

## Python

``````class Solution:
def maximalSquare(self, matrix: List[List[chr]]) -> int:
m = len(matrix)
n = len(matrix[0])
dp = [0] * n
maxLength = 0
prev = 0  # dp[i - 1][j - 1]

for i in range(m):
for j in range(n):
cache = dp[j]
if i == 0 or j == 0 or matrix[i][j] == '0':
dp[j] = 1 if matrix[i][j] == '1' else 0
else:
dp[j] = min([prev, dp[j], dp[j - 1]]) + 1
maxLength = max(maxLength, dp[j])
prev = cache

return maxLength * maxLength
``````