Find Kth largest element in an array I am preparing for interviews where my code would be judged based on optimizations, OOP concepts, code readability as well as my knowledge of JAVA and design patterns.

What comments will you give in code review for the below code?

This is my code for Kth Largest element in an Array. 
The logic is to create a K size max heap, and then add the smallest K elements to the heap.
Total array size can be equal to INT_MAX and k can be as small as 2

import java.util.Comparator;
import java.util.PriorityQueue;


public class CustomArray {

    class DecreasingComparator implements Comparator&lt;Long&gt; {

        @Override
        public int compare(Long firstNumber , Long secondNumber) {
            return (int) (secondNumber - firstNumber);
        }
    }

    public long findKthLargestElement(long[] input, int k) {
        if(k &lt; 1 || k &gt; input.length) {
            throw new IllegalArgumentException("Invalid k, should be between 1 and arra length");
        }

        PriorityQueue&lt;Long&gt; heap = new PriorityQueue&lt;&gt;(k, new DecreasingComparator());

        for(int i=0; i&lt;k;i++) {
            heap.add(input[i]);
        }
        for(int i=k; i&lt;input.length;i++) {
            if(heap.peek() &gt; input[i]) {
                heap.poll();
                heap.add(input[i]);
            }
        }

        return heap.poll();
    }
}
Total array size can be equal to INT_MAX and k can be as small as 2


Why not 1?



    @Override
    public int compare(Long firstNumber , Long secondNumber) {
        return (int) (secondNumber - firstNumber);
    }


I found myself several time staring at such a line and being sure, there can be NPE there! But it can and I'd suggest to add explicit checks (throwing is correct, my point is to do it explicitly).

The Comparator is seriously broken:


casting from long to int can overflow
subtraction can overflow, too


Use Long.compare.



PriorityQueue&lt;Long&gt; heap = new PriorityQueue&lt;&gt;(k, new DecreasingComparator());


That makes it simple, but boxing is not free. While a few small values get cached in a cache in java.lang.Long, for others an object must be created. This takes 16 bytes and the heap contains a reference to it (4 or 8 bytes). So you need 20 or 24 bytes per long in addition to the 8 it takes in the input array.

This may make a few megabytes if you want the millionth element. There's also an allocation, but with current smart GCs it's usually no big deal.



There's no need for a decreasing comparator, as you could find the input.length+1-kth smallest element instead.

Or you could use both and select the one giving you a smaller queue.



    for(int i=0; i&lt;k;i++) {
        heap.add(input[i]);
    }
    for(int i=k; i&lt;input.length;i++) {
        if(heap.peek() &gt; input[i]) {
            heap.poll();
            heap.add(input[i]);
        }
    }


This is smart and avoids most of the boxing (for small k). It could use some comments and a lot of tests.