Kth largest element in the unsorted array

Posted: 20 Nov, 2020
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

You are given an array consisting of 'N' distinct positive integers and a number 'K'. Your task is to find the kth largest element in the array.

Example:
Consider the array {2,1,5,6,3,8} and 'K' = 3, the sorted array will be {8, 6, 5, 3, 2, 1}, and the 3rd largest element will be 5.
Note:
1) Kth largest element in an array is the kth element of the array when sorted in non-increasing order. 

2) All the elements of the array are pairwise distinct.
Input Format:
The first line of the input contains an integer 'T' denoting the number of test cases.

The first line of each test case contains two space- separated integers 'N' and 'K', as described in the problem statement.

The second line of each test case contains 'N' space-separated integers, representing the elements of the array.
Output Format:
For each test case, print a single integer denoting the kth largest number in the given array.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 100
1 <= N <= 10^4
1 <= ARR[i] <= 10^9
1 <= K <= N

Time Limit: 1 sec
Approach 1
  • The most obvious brute force approach would be to sort the array in descending order and return the ‘K’th element from the beginning of the array.
  • Sort the array in descending order, for sorting most of the languages have their inbuilt sort methods which are usually very fast.
  • After sorting, return the element arr['K'-1](i.e. element at index ‘K’-1, considering 0-based indexing).
Try Problem