JAVA DP In place solution


  • 0

    Since we use constant space, the overhead of judgement is kind of higher than the others which use O(n) space.

    public int maximalSquare(char[][] matrix) {
        int n=matrix.length;
        if(n==0) return 0;
        int m=matrix[0].length;
        int max=0;
        int[] corner=new int[3];
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                Arrays.fill(corner,0);
                if(i-1>=0) corner[0]=matrix[i-1][j]-'0';
                if(j-1>=0) corner[1]=matrix[i][j-1]-'0';
                if(i-1>=0&&j-1>=0) corner[2]=matrix[i-1][j-1]-'0';
                if(matrix[i][j]!='0')
                {
                    for(int a=1;a<3;a++) if(corner[0]>corner[a]) corner[0]=corner[a];
                    matrix[i][j]+=corner[0];
                }
                if(matrix[i][j]-'0'>max) max=matrix[i][j]-'0';
            }
        }
        return max*max;
    }

Log in to reply
 

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