Last Updated: 20 Nov, 2020
Kth largest element in the unsorted array
Moderate
Asked in companies
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
Approaches
- 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).
- We can use some data structures to reduce the time complexity. Notice the fact that if there are only ‘K’ elements in the array, then the ‘K’th largest element will be nothing but the smallest element of that array. This observation clearly hints at using heaps as they help find either the minimum or maximum element efficiently.
- We will be using a min-heap as we are interested in the smallest element among the ‘K’ largest elements of the array. In most of the programming languages, heaps are implemented using priority queues.
- Maintain a priority queue giving priority to the min element( Min-heap), and insert the first ‘K’ elements of the array into the priority queue.
- Now traverse the remaining ‘N - K’ elements one by one and check if the element at the top of the priority queue is smaller than the element being traversed then pop the element present at the top of the queue and insert the element being traversed in the priority queue. And do the same for all the ‘ N - K ’ elements. We want to make sure that at any instance our queue will only have ‘K’ elements.
- After performing the above operation, return the element at the top of the priority queue, which will be our answer. Because after performing the above operations the priority queue will be containing the ‘K’ largest elements of the array. And the min of these ‘K’ elements will be the kth largest element which will be present at the top of the queue because we are maintaining a min priority queue (min-heap).
- Lets examine the working of the above algorithm with the help of an example:
Consider the array {2,3,4,8,1,7,5,6} and let ‘K’ =4.
Lets take an empty priority queue(min heap)
- After performing the first step of the algorithm the queue will be:
2-3-4-8 (in the same order i.e. 2 will be at the top of the queue and 8 at the bottom).
- Now we start traversing the rest of the ‘N - K’ elements i.e step2 of the algorithm.
- We start form 1, since it is smaller than 2 so we will continue.
- Then we come to 7, since it is greater than 2 so we will pop the element from the top(2) and push 7 into the queue. Now, queue will be like 3-4-7-8(in the same order).
- Then we come to 5, since it is greater than 3 so we will pop the element from the top of the queue(3) and push 5 into the queue. Now, queue will be like 4-5-7-8 (in the same order).
- Then we come to 6, since it is greater than 4 so we will pop the element from the top of the queue(4) and push 6 into the queue. Now, queue will be like 5-6-7-8 (in the same order).
- After completing this step we can observe that our queue contains the 4 largest elements of the array with the 4th largest element at the top of the queue.
- Now we return the element at the top of the queue(5) which is our answer.
Similar problems