Kth Largest Element in an Array

Find the kth largest element in an unsorted array. 

Example 1:

Input: [3,2,1,5,6,4] and k = 2
Output: 5

Approach

Java

import java.util.Arrays;

public class FindKthLargest {

    public static void main(String[] args) {

        int nums[] = { 3, 2, 1, 5, 6, 4 };

        int k = 2;

        System.out.println(findKthLargest(nums, k));

    }

    public int findKthLargest(int[] nums, int k) {

        Arrays.sort(nums);

        for (int i = nums.length - 1; i > 0; i--) {

            k--;

            if (k == 0)

                return nums[i];

        }

        return nums[0];

    }

}

C++

#include <bits/stdc++.h>

using namespace std;

//function to find the kth 

//largest number in an array

int findKthLargest(int nums[], int n,int k)

{

     sort(nums,nums+n);

    for (int i = n - 1; i > 0; i--) 

      {

            k--;

            if (k == 0)

                return nums[i];

    }

    return nums[0];

}

int main()

{

    int nums[] = { 3, 2, 1, 5, 6, 4 };

    int n=sizeof(nums)/sizeof(nums[0]);

    int k = 2;

    cout<<findKthLargest(nums, n,k)<<"\n";

    return 0;

}

Approach: Using a priority queue  (min priority queue in c++)

Java

import java.util.PriorityQueue;

public class FindKthLargest {

    public static void main(String[] args) {

        int nums[] = { 3, 2, 1, 5, 6, 4 };

        int k = 2;

        System.out.println(findKthLargest(nums, k));

    }

    public static int findKthLargest(int[] nums, int k) {

        PriorityQueue<Integer> pq = new PriorityQueue<>();

        for (int i = 0; i < k; i++) {

            pq.add(nums[i]);

        }

        for (int i = k; i < nums.length; i++) {

            if (nums[i] > pq.peek()) {

                // replacing with root if new value is large

                pq.poll();

                pq.add(nums[i]);

            }

        }

        // out of k values it will return largest value

        return pq.peek();

    }

}

C++

#include <bits/stdc++.h>

using namespace std;

//function to find the kth

//largest number in an array

int findKthLargest(int nums[], int n,int k) 

 {

  //min priority queue

   priority_queue<int,vector<int>,greater<int> > pq;

   //push k elements into the priority queue

   for (int i = 0; i < k; i++) {

            pq.push(nums[i]);

        }

    for (int i = k; i <n; i++) 

      {

            if (nums[i] > pq.top() )

            {

                // replacing with root if new value is large

                pq.pop();

                pq.push(nums[i]);

            }

        }

        // out of k values it will return largest value

        return pq.top();

}

int main()

{

    int nums[] = { 3, 2, 1, 5, 6, 4 };

    int n=sizeof(nums)/sizeof(nums[0]);

    int k = 2;

    cout<<findKthLargest(nums, n,k)<<"\n";

    return 0;

}