Find K’th largest element in an array

Given an array and positive integer k, find K’th largest element in the array.


For example,

Input:

arr = [7, 4, 6, 3, 9, 1]
k = 2

Output:

K’th largest element in the array is 7

 


 

A simple solution would be to use a efficient sorting algorithm to sort the array in descending order and return the element at (k-1)th index. The worst case time complexity of this approach will be O(nlogn) where n is the size of the input array.
 

Approach 1 (Using Min Heap) –

We can easily solve this problem in O(nlogk) by using a min-heap. The idea is to construct a min-heap of size k and insert first k elements of array (A[0..k-1]) into the heap. Then for each of the remaining element of the array (A[k..n-1]), if that element is more than the root of the heap, we replace the root with current element. We repeat this process till array is exhausted. Now we will be left with k largest elements of the array in the min-heap and k’th largest element will reside at the root of the min-heap.

 
C++ implementation –
 

Download   Run Code

Output:

K’th largest element in the array is 7

 

Approach 2 (Using Max Heap) –

We can easily solve this problem in O(klogn) by using a max-heap. The idea is to simply construct a max-heap of size n and insert all elements of the array (A[0..n-1]) into it. Then we pop first k-1 elements from it. Now k’th largest element will reside at the root of the max-heap.

 
C++ implementation –
 

Download   Run Code

Output:

K’th largest element in the array is 7

 

Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂