Kth largest element

Moderate

0/80

17 upvotes

Asked in companies

Problem statement

Ninja loves playing with numbers. One day Alice gives him some numbers and asks him to find the Kth largest value among them.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

2
5 2
1 2 2 3 4
5 3
10 11 23 23 23

Sample Output 1:

3
23

Explanation for Sample Input 1:

In the first test case, out of the given elements, the first largest is 4, and the second largest is 3. So we return 3 as our answer.

In the second test case,  out of the given elements, the first largest is 23, the second largest is 23, and the third-largest is 23. So we return 23 as our answer.

Sample Input 2:

2
7 2
1 2 3 4 5 6 7
8 4
3 4 6 9 5 10 11 12

Sample Output 2:

6
9

Hint 1

Hint 2

Can you sort the elements.

Approaches (2)

Approach 1

Approach 2

Sorting

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.

Time Complexity

O(N*logN), where ‘N’ is the total number of elements in the given array.

As Sorting takes N*LogN complexity, so the overall complexity is O(N*logN).

Space Complexity

O(1), no extra space required.

As we are not using any extra space. Hence, the overall space complexity is O(1).

(100% EXP penalty)

Kth largest element

Console