Getting incorrect sort order

Question

Failing test case:

• Input: [-2147483648,1,1]

• Output: -2147483648

• Expected: 1

Why is the output expected as 1 when -2147483648 is the 2nd max number here?

public int thirdMax(int[] nums) {

    PriorityQueue<Integer> pq = new PriorityQueue(new Comparator<Integer>(){
        public int compare(Integer a, Integer b){return b-a;}
    });

    int res=0;

    for(int num : nums){
        if(!pq.contains(num)  )
            pq.add(num);

    }

    if(pq.size()<=2){
       for(int i=0; i<pq.size(); i++){
            res=pq.poll();
        }             
    }
    else {
        for(int i=0; i<3; i++){
            res=pq.poll();
        }        
    }
    return res;   
}

Answer 1

Your method of comparing isn't correct for int.

Rather than:

return b - a;

you should do:

return Integer.compare(b, a);

An int can only hold values of up to Integer.MAX_VALUE. But if you do 1 - -2147483648, the result is greater than Integer.MAX_VALUE, which makes it negative again - and you get wrong sort orders as a result. Basically, return b - a; is only safe if you know that all numbers are positive (or if the numbers won't be further apart than Integer.MAX_VALUE).

In other cases, you can use the API method Integer.compare.

Note that, since you are comparing by the inverse of the natural order of integers, you can also shorten your code with:

PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());