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++)
                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';
                    for(int a=1;a<3;a++) if(corner[0]>corner[a]) corner[0]=corner[a];
                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.