# Detailed explanation with easy Java code, beats 80%. O(m*n) time and space

• ``````public class Solution {
public static int maximalSquare(char[][] matrix) {
//Main idea: dynamic programming
//base case: M[i][j] = matrix[i][j]  if i==0 || j==0
//subproblem: M[i][j] = min(M[i-1][j],M[i][j-1],M[i-1][j-1])+1  if matrix[i][j]==1
//                    = 0    if matrix[i][j] = 0
//at the same time, update max when larger than max

//corner case
if(matrix == null || matrix.length == 0) {
return 0;
}

int max = 0;
int row = matrix.length;
int col = matrix[0].length;
int[][] M = new int[row][col];

//base case1: first row
for(int j = 0; j < col; j++) {
M[0][j] = matrix[0][j]-'0';
if(M[0][j] == 1) {
max = 1;
}
}
//base case2: first col
for(int i = 1; i < row; i++) {
M[i][0] = matrix[i][0]-'0';
if(M[i][0] == 1) {
max = 1;
}
}

//induction rule
for (int i = 1; i < row; i++) {
for (int j = 1; j < col; j++) {
if(matrix[i][j]-'0' == 0) {
M[i][j] = 0;
}
else{
M[i][j] = Math.min(M[i-1][j], M[i][j-1]);
M[i][j] = Math.min(M[i][j], M[i-1][j-1]);
M[i][j]++;
//update max when necessary
max = Math.max(max,M[i][j]);
}
}
}
return max*max;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.