# 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

#### Approach 1: Sorting

A simple solution would be to use an 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 2: 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++

Output:

K’th largest element in the array is 7

## Java

Output:

K’th largest element in the array is 7

#### Approach 3: Using Max Heap

We can easily solve this problem in O(n + 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++

Output:

K’th largest element in the array is 7

## Java

Output:

K’th largest element in the array is 7

#### Approach 4: Using std::nth_element

We can easily solve this problem by using std::nth_element. Special thanks to Jeremy Faller for sharing this approach in comments. The prototype of std::nth_element is –

void nth_element (RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);

It rearranges the elements in the range [first,last), in such a way that the element at the nth position is the element that would be in that position in a sorted sequence.

std::nth_element is typically implemented using a version of quickselect called Introselect. Introselect is a hybrid of quickselect and median of medians. If quickselect takes too long (bad pivot selection) then it falls back to the slower but guaranteed linear time algorithm thus capping its worst case runtime before it becomes worse than linear.

C++ implementation –

Output:

K’th largest element in the array is 7

(1 votes, average: 5.00 out of 5)

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂

Subscribe
Notify of
Guest
isruslan

Approach 5: quickselect

https://gist.github.com/isRuslan/3a0d69aaeed2bde53a8fd53bbffd5031

– select pivot and partition array on left ( pivot) arrays
– check if left is k – 1 length => pivot is k – smallest element
– else:
– run again for (left, k) if left > k – 1
– or (right, k – len(left) – 1) if left < k – 1, where k – len(left) – 1 is the number of elements that need to find before k smallest.

Guest
Ozan Bulut

In approach 3, inserting all elements into priority queue one by one takes o(nlogn) time. You should pass the vector to the constructor for o(n) time complexity.

Guest
Jeremy Faller

If you just use the correct function in the standard library, it’s much faster:

Guest

I doubt if approach 2 is O(klogn) and not O(nlogn). considering worst case such as say 1,2,3,4,5,6,7,8 and k = 3. there would be total of 8 (i.e. n) heap insertions and 5 pops.