# Java 12ms 30 lines O(m*n) solution

• This problem is tagged as dynamic programming. The question is how to use dp.
I use a matrix called maxsqr to memorize the length of a square whose bottom right corner is at [i] [j].
For the cells at the top or at the left border of the entire matrix, since there are no cell sitting at their left hand side or top. Once matrix[i][j] == '1', maxsqr[i][j] = 1 (i==0 or j==0).
For the rest cells, if matrix[i][j] is 1, the cells on its top, left and top-left need to be checked. Those cells record the max number of contiguous '1's can be reached by the current cell's neighbor.
The minimum of those 3 cells + 1 is the value of the current cell (maxsqr[i][j]).
Keep refreshing maxedge using maxsqr[i][j] to track the longest edge of the square and done!.

public int maximalSquare(char[][] matrix) {
int maxedge = 0;//max length of the edge of one square
int m = matrix.length;
if(m==0) return 0;
int n = matrix[0].length;
if(n==0) return 0;
int[][] maxsqr = new int[m][n];
//initialize cells on top and left.
//top
for(int i = 0;i<m;i++){
if(matrix[i][0]=='1'){
maxsqr[i][0] = 1;
maxedge = maxedge>maxsqr[i][0]?maxedge:maxsqr[i][0];
}
}
//lhs
for(int j = 0;j<n;j++){
if(matrix[0][j]=='1'){
maxsqr[0][j] = 1;
maxedge = maxedge>maxsqr[0][j]?maxedge:maxsqr[0][j];
}
}
if(m>1&&n>1){
for(int i = 1;i<m;i++){
for(int j = 1;j<n;j++){
if(matrix[i][j]=='1'){
int mineighbor = Math.min(Math.min(maxsqr[i-1][j-1],maxsqr[i][j-1]),maxsqr[i-1][j]);
maxsqr[i][j] = mineighbor + 1;
maxedge = maxedge>maxsqr[i][j]?maxedge:maxsqr[i][j];
}
}
}
}
return maxedge*maxedge;
}

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