Last Updated: 15 Oct, 2020
Kth largest element
Moderate
Asked in companies
Ninja loves playing with numbers. One day Alice gives him some numbers and asks him to find the Kth largest value among them.
Input Format:
The first line of input contains an integer ‘T,’ denoting the number of test cases. The test cases follow.
The first line of each test case contains two space-separated integers, ‘N’ and ‘K’, denoting the number of elements in the array and the index of the largest number to be found respectively.
Output Format:
For each test case, print an integer denoting the Kth largest number.
Print the output of each test case in a separate line.
Note:
You are not required to print the expected output; it has already been taken care of. Just implement the function.
Constraints:
1<= T <= 50
1 <= K <= N <= 10^4
1 <= array[i] <= 10^5
Time Limit: 1 sec
Approaches
The idea is to sort the elements and return the kth largest element among them.
The steps are as follows:
- Sort the elements in descending order.
- Return the element at k - 1 th index.
We can insert the elements in a priority queue and remove the k top elements to get our desired result.
The steps are as follows:
- Initialize a priority queue ‘elementsInserted’ to store the elements based on priority.
- We will iterate from i = 0 to N:
- If k elements are already inserted in ‘elementsInserted’ then we check if array[i] is greater than equal to the top element of ‘elementsInserted’, then we remove an element from ‘elementsInserted’ and insert array[i] in ‘elementsInserted’.
- Else we just insert array[i] in ‘elementsInserted’.
- Finally, we return the topmost element of the ‘elementsInserted’ as our final answer.