Java, Finding Kth largest value from the array [duplicate]

Question

I had an interview with Facebook and they asked me this question.

Suppose you have an unordered array with N distinct values

$input = [3,6,2,8,9,4,5]

Implement a function that finds the Kth largest value.

EG: If K = 0, return 9. If K = 1, return 8.

What I did was this method.

private static int getMax(Integer[] input, int k)
{
    List<Integer> list = Arrays.asList(input);
    Set<Integer> set = new TreeSet<Integer>(list);

    list = new ArrayList<Integer>(set);
    int value = (list.size() - 1) - k;

    return list.get(value);
}

I just tested and the method works fine based on the question. However, interviewee said, in order to make your life complex! lets assume that your array contains millions of numbers then your listing becomes too slow. What you do in this case? As hint, he suggested to use min heap. Based on my knowledge each child value of heap should not be more than root value. So, in this case if we assume that 3 is root then 6 is its child and its value is grater than root's value. I'm probably wrong but what you think and what is its implementation based on min heap?

Answer 1

He has actually given you the whole answer. Not just a hint.

And your understanding is based on max heap. Not min heap. And it's workings are self-explanatory.

In a min heap, the root has the minimum (less than it's children) value.

So, what you need is, iterate over the array and populate K elements in min heap. Once, it's done, the heap automatically contains the lowest at the root.

Now, for each (next) element you read from the array, -> check if the value is greater than root of min heap. -> If yes, remove root from min heap, and add the value to it.

After you traverse your whole array, the root of min heap will automtically contain the kth largest element.

And all other elements (k-1 elements to be precise) in the heap will be larger than k.

Answer 2

Here is the implementation of the Min Heap using PriorityQueue in java. Complexity: n * log k.

import java.util.PriorityQueue;

public class LargestK {

  private static Integer largestK(Integer array[], int k) {
    PriorityQueue<Integer> queue = new PriorityQueue<Integer>(k+1);
    int i = 0;
    while (i<=k) {
      queue.add(array[i]);
      i++;
    }
    for (; i<array.length; i++) {
      Integer value = queue.peek();
      if (array[i] > value) {
        queue.poll();
        queue.add(array[i]);
      }
    }
    return queue.peek();
  }

  public static void main(String[] args) {
    Integer array[] = new Integer[] {3,6,2,8,9,4,5};
    System.out.println(largestK(array, 3));
  }
}

Output: 5

The code loop over the array which is O(n). Size of the PriorityQueue (Min Heap) is k, so any operation would be log k. In the worst case scenario, in which all the number are sorted ASC, complexity is n*log k, because for each element you need to remove top of the heap and insert new element.