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


  • -1
    C

    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;
    }

  • 0
    A

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


Log in to reply
 

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