# [No DP]. Everybody is talking DP here. But, I can crack this Puzzle without DP. Upvote me!!!!

• I don't know if you guys solve the issue Puzzle 303 or not. I am using the same idea.
First, we need to build a double-dimension array 'data' as you can see in my code. data[i][j] means sum from matrix[i][0]~maxtrix[i][j].
You may find out that a square will have all cell set to 1. If the length of a valid square is n, the count of 1 in this square should be n*n. Otherwise, it is not a valid square.

What I am doing here is to count every possible squares in the map. And if the number of 1 in the square matches square of its length, we update the result.

It will be extremely easy to calculate the sum of a square by using 'data' array. We just need to add up the difference between its right edge and its left edge. For example square (1,1,3,3) is data[1][3]-data[1][1]+data[2][3]-data[2][1]+data[3][3]-data[3][1];

``````public int maximalSquare(char[][] matrix) {
if(matrix.length==0||matrix[0].length==0) return 0;
int height=matrix.length,width=matrix[0].length,start=1,end=height>width?width:height;
int [][] data=new int[height][width+1];
for(int i=0;i<height;i++)
for(int j=1;j<=width;j++)
data[i][j]=(matrix[i][j-1]=='1'?1:0)+data[i][j-1];
int max=0,count;
boolean find;
for(int edge=start;edge<=end;edge++){
find=false;
for(int row=0;row<=height-edge&&find==false;row++)
for(int column=0;column<=width-edge&&find==false;column++){
count=0;
for(int i=0;i<edge;i++){
count+=data[row+i][column+edge]-data[row+i][column];
}
if(count==edge*edge) find=true;
}
if(find==true) max=edge;
}
return max*max;
}``````

• @chenyuan53618 Worst case O(n^4) time?

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