@StefanPochmann I signed back on just now to retract my statement. I was confused when I wrote my original comment last night. Your solution is good. If I'm correct, it runs in n * log(3) time, which is linear.

@mlaw0 I think your complexity is k*n, which k is 3 in this case, n is the complexity of max(nums). I think the idea of this problem is to encourage to use quick sort or heap. But the problem is kind of vague.

public int thirdMax(int[] nums) {
TreeSet<Integer> set = new TreeSet();
for (int num : nums)
if (set.add(num) && set.size() > 3)
set.pollFirst();
return set.size() > 2 ? set.pollFirst() : set.pollLast();
}