class Solution {
public int maximalSquare(char[][] matrix) {
if (matrix.length == 0)
return 0;
int m = matrix.length, n = matrix[0].length, max = 0;
int dp[][] = new int[m][n];
// dp[i][j] -> length of biggest square possible with lower right corner at i,j
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 || j == 0)
dp[i][j] = matrix[i][j] == '1' ? 1 : 0;
else if (matrix[i][j] == '1')
dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1]));
max = Math.max(max, dp[i][j]);
}
}
return max * max;
}
}