Problem

Submissions

Hints & solutions

Discuss

Kth largest element in the unsorted array

Moderate

0/80

Average time to solve is 10m

Contributed by

31 upvotes

Asked in companies

Problem statement

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.

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

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

Sample Input 1:

1
3 1
1 2 3

Sample Output 1:

Explanation for sample input 1:

3 is the first largest element in the array {1,2,3}.

Sample Input 2:

1
4 2
5 6 7 8

Sample Output 2:

Explanation for sample input 2:

7 is the second largest element in the array {5,6,7,8}.

Hint 1

Hint 2

Sort the array.

Approaches (2)

Approach 1

Approach 2

Brute Force

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).

Time Complexity

O( N * log(N) ), where ‘N’ is the size of the array.

We can sort an array in O(N * log(N)).

Space Complexity

O(1).

No extra space is used.

(75% EXP penalty)

(100% EXP penalty)

Kth largest element in the unsorted array

Console