Kth Largest Element

Medium Kth Largest Element

19%

Accepted

Find K-th largest element in an array.

Have you met this question in a real interview? 

Yes

Example

In array [9,3,2,4,8], the 3rd largest element is 4.

In array [1,2,3,4,5], the 1st largest element is 5, 2nd largest element is 4, 3rd largest element is 3 and etc.

Note

You can swap elements in the array

Challenge

O(n) time, O(1) extra memory.

class Solution {

    //param k : description of k

    //param numbers : array of numbers

    //return: description of return

    public int kthLargestElement(int k, ArrayList<Integer> numbers) {

        // write your code here

         if (k > numbers.size()) return 0;

        return quickSort(0, numbers.size()-1, numbers, k);

    }

    

    private int quickSort(int start, int end, ArrayList<Integer> numbers, int k){

        int pivot = numbers.get(start);

        int idx = start;

        int right = end;

        start++;

        while(start <= end){

            while(start <= end && numbers.get(start) >= pivot) start++;

            while(start <= end && numbers.get(end) <= pivot) end--;

            if(start < end){

                swap(start, end, numbers);

            }

        }

        swap(idx, end, numbers);

        if(end+1 == k){

            return pivot;

        } else if(end+1 > k){

            return quickSort(idx, end-1, numbers, k);

        } else return quickSort(end+1, right, numbers, k);

        

    }

    

    private void swap(int start, int end,  ArrayList<Integer> numbers){

                int temp = numbers.get(start);

                numbers.set(start, numbers.get(end));

                numbers.set(end, temp);

    }

    

};

class Solution {
    //param k : description of k
    //param numbers : array of numbers
    //return: description of return
    public int kthLargestElement(int k, ArrayList<Integer> numbers) {
        // write your code here
        if(numbers.size() < k) return 0;
         PriorityQueue queue = new PriorityQueue(numbers.size(),  Collections.reverseOrder());
         
         for(int num : numbers){
             queue.add(num);
         }
         
         while(k-- > 1 ){
             queue.poll();
         }
         return (int) queue.poll();
         
    }
    

};