Last Updated: 30 Dec, 2020
K Largest Element
Moderate
Asked in companies
You are given an unsorted array containing ‘N’ integers. You need to find ‘K’ largest elements from the given array. Also, you need to return the elements in non-decreasing order.
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 positive integers ‘N’ and ‘K’ denoting the number of the elements present in the array and count of the largest elements you need to return as the answer respectively.
The second line of each test case contains ‘N’ space-separated integers denoting the elements of the array.
Output Format:
The only line of output of each test case should contain ‘K’ largest elements in the array in non-decreasing order.
Print the output of each test case in a separate line.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Follow Up:
Can you solve this in less than O(N*log(N)) time complexity?
Constraints:
1 <= T <= 100
1 <= N <= 10^4
1<= K <= N
-10^9 <= ARR[i] <= 10^9
Where ‘T’ is the number of test cases, ‘N’ is the size of the array, ‘K’ is the number of elements you need to return as an answer and ARR[i] is the size of the array of elements.
Time Limit: 1 sec
Approaches
- We can use bubble sort or any other sorting algorithm with some changes to solve this problem.
- In bubble sort we have two loops:- inner loop for swapping the elements and take the highest element to the end of the remaining unsorted array and an outer loop for performing that operation ‘N’ so that array becomes sorted.
- If we run the outer loop for ‘K’ times then we have ‘K’ largest element at the end of the array. Thus we simply take those ‘K’ elements and return them because they are already sorted in non-decreasing order as well.
- We can improve our sorting using some efficient sorting algorithms like Merge sort or Heap sort etc.
- Sort the whole array in decreasing order and take out the first ‘K’ elements one by one to return as the answer.
- We can use the Heap data structure to store the elements in the sorted order. The problem can be solved by both Min heap and Max heap but for simplicity, we will Min heap.
- We will insert the first ‘K’ elements of the array in the min-heap. The idea here is that we maintain the min-heap in such a way that at any point of time it will contain the ‘K’ largest elements present till now.
- We traverse on the remaining elements and for each element, we compare it with the top of the min-heap. Remember that the top of the min-heap is the lowest among the elements present in the heap. So if our current element is greater than the top of the min-heap then it means that the top of the heap is not the part of K largest element because the current element is itself greater than the top so we should remove the top of the heap and insert our current element in place of it.
- Finally, after traversing the whole array the heap will contain the K largest elements in it. So we pop the top of the heap one by one and store them in an array as our final answer.
- We can break this problem into two parts:
- In the first part, we find the Kth largest element in the array.
- In the second part, we take ‘K’-1 elements which are greater than or equal to Kth largest element to form an array of ‘K’ largest elements
- To find Kth largest element we can use a quick sort algorithm. First, we choose a random pivot and define its position in a sorted array in a linear time. This could be done with the help of a partition algorithm.
- To implement partition we move along the array and compares each element with a pivot, and moves all elements smaller than the pivot to the left of the pivot.
- As a result, we have an array where the pivot is in its perfect position in the ascending sorted array, all elements on the left of the pivot are smaller than the pivot, and all elements on the right of the pivot are larger or equal to the pivot.
- Hence the array is now split into two parts. Here there is no need to deal with both parts as we do in the actual quicksort because we can count how many elements are greater than pivot by the difference of indexes of the pivot and right boundary of the array.
- If that count is equal to ‘K’ then it means pivot is the Kth largest else if the count is less than ‘K’ then it means the Kth largest element lies on the right side of the pivot else on the left side of the pivot.
- So we move to the correct part and find the Kth largest element. Then we traverse on the array and store remaining ‘K’-1 elements which are greater than equal to Kth largest element. We sort our final array and return it as the answer.
Similar problems