# 2 Java Solutions, both DP, 308ms and 348ms

• solution 1: 308ms,

``````public class Solution {
public int maximalSquare(char[][] matrix) {
int m = matrix.length;
if(m==0) return 0;
int n = matrix[0].length;
int[][] A = new int[m][n];
int sqr = 0;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(matrix[i][j]=='0') A[i][j]=0;
else A[i][j]=i==0||j==0?1:Math.min(Math.min(A[i-1][j],A[i][j-1]),A[i-1][j-1])+1;
sqr = Math.max(sqr,A[i][j]*A[i][j]);
}
}
return sqr;
}
}
``````

solution 2: 348ms

``````public class Solution {
public int maximalSquare(char[][] matrix) {
int m = matrix.length;
if(m==0) return 0;
int n = matrix[0].length;
int[][] height = new int[m][n];
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(matrix[i][j]=='0') height[i][j]=0;
else height[i][j]=i==0? 1:height[i-1][j]+1;
}
}
int max = 0;
for(int i=0;i<m;i++){
max = Math.max(max,maxSquare(height[i]));
}
return max;
}
private int maxSquare(int[] height){
int i=0, j=0, min=height[0], sqr=0, len=0;
while(j<height.length&&i<=j){
min = height[i];
for(int k=i+1;k<j+1;k++){
min = Math.min(min,height[k]);
}
len = Math.min(min,j-i+1);
sqr = Math.max(sqr,len*len);
if(min<j-i+1){
i=j-min+1;
}
j++;
}
return sqr;
}
}``````

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