# 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<Long> {

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

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

PriorityQueue<Long> heap = new PriorityQueue<>(k, new DecreasingComparator());

for(int i=0; i<k;i++) {
}
for(int i=k; i<input.length;i++) {
if(heap.peek() > input[i]) {
heap.poll();
}
}

return heap.poll();
}
}

• Seeing that you are preparing for interviews, I would ask you some questions also, if I may. Is there a particular reason why you chose this approach? What would you have chosen if the question included also the request to not use extra (as in: dependent from n or k) space, in other words, the space complexity is required to be O(1)? Commented Jun 2, 2015 at 21:04
• Just to be clear, seeing that from the comment it can be misunderstood, I meant the extra space complexity should be O(1) and not the total space complexity. Commented Jun 2, 2015 at 21:25
• If you're interested in performance, there are better algorithms for this. Lookup selection algorithms, esp quick select, on Wikipedia.
– Joni
Commented Jun 4, 2015 at 6:15

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<Long> heap = new PriorityQueue<>(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<k;i++) {
}
for(int i=k; i<input.length;i++) {
if(heap.peek() > input[i]) {
heap.poll();
}
}


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

• Thanks for the review. Can you please elaborate on "That makes it simple, but boxing is not free." Commented Jun 2, 2015 at 17:22
• If I understood well what @maaartinus meant, he refers to the fact that long is a primitive type while Long is an object, so extra memory (and extra work) is needed to manage it. Commented Jun 2, 2015 at 20:33
• @GentianKasa Exactly. I've updated my answer but forgot to reply to the comment. Commented Jun 2, 2015 at 20:37
• ok.. but PriorityQueue does require an object, it cannot work with long, how can I save the memory used due to boxing? Commented Jun 3, 2015 at 11:09
• @learner By writing your own heap using longs. It's not hard as there are just two operations (+ resizing, unless you can modify the original array) and it may take maybe one hour. Using the j.u.PQ is surely not a bad choice as it saves you this time, but you should know the cost and the alternatives. And there's more. Commented Jun 3, 2015 at 11:28

In Java 8, you can use Comparator.reverseOrder() instead of writing a custom comparator to do reverse sorting. You would then also avoid the potential overflow from subtracting and casting.

PriorityQueue<Long> heap = new PriorityQueue<>(k, Comparator.reverseOrder());


The class is named CustomArray but there is no visible reason why. Even Solver would be a better name, because this class certainly is not a custom array.

The class DecreasingComparator should be static, as it makes no reference to members of the enclosing class. And you don't need to create a new instance of this class every time you want to find a kth element. You could have just one instance and reuse it, since the class has no data, only logic. Of course, as 200_success already said, no need for a custom implementation at all.

This version uses Java 8's streams. I think it is relatively easy to understand, and I think that accounts for a lot in an interview. Sort array and take kth element (skip input.length - k to account for reverse order).

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

return Arrays.stream(input)
.sorted()
.findFirst()              // retrieve element
.getAsLong();             // no need for optional long, just return value
}


Using Java streams shows that you understand how they work and that you keep up with technology, even if they don't use Java 8 (or above, if and when they come out). They might feel that you could teach something to the programmers already hired.