K Largest Element
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

Question

K Largest Element

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

Accepted Answer

To solve the question using a max heap, make a max heap of all the elements of the list. Run a loop for k-1 times and remove the top element of the heap. After running the loop, the element at top will be the kth largest element, return that. Time Complexity : O(n + klogn)
The question can also be solved using a min heap.

Approach:
1. Create a min heap class with a capacity of k
2. When the heap reaches capacity eject the minimum number.
3. Loop over the array and add each number to the heap.
4. At the end, the largest k number of elements will be left in the heap, the smallest of them being at the top of the heap, which is the kth largest number
The time complexity for this solution is O(N logK).

Accepted Answer

Bubble sort

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.

Space Complexity: O(1)Explanation:

O(1).

The output array does not count as extra space for the purpose of space complexity analysis. Hence, the overall space complexity is O(1).

Time Complexity: O(1)Explanation:

O(N*K), where ‘N’ is the number of elements present in the array and ‘K’ is the count of the largest elements.

As we ran two nested outer loops till K and inner loop till ‘N’. Hence, the overall time complexity is O(N*K).

Accepted Answer

Sorting

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.

Space Complexity: O(1)Explanation:

O(N), where ‘N’ denotes the number of elements present in the array.

The merge sort or heap sort takes linear space if you use these sorting algorithms for sorting. Hence, the overall space complexity is O(N).

Time Complexity: O(1)Explanation:

O(N * log(N)), where ‘N’ denotes the number of elements present in the array.

The merge sort or heap sort takes N*log(N) time if you use these sorting algorithms for sorting. Hence, the overall time complexity is O(N * log(N)).

Accepted Answer

Heap data structure

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.

Space Complexity: O(1)Explanation:

O(K), where K denotes the count of the largest elements.

We used a heap of size ‘K’. Hence, the overall space complexity is O(K).

Time Complexity: O(1)Explanation:

O(N * log(K)), where ‘N’ denotes the number of elements present in the array and ‘K’ is the count of the largest elements.

For ‘N’ elements, on each iteration, the heap will contain at most ‘K’ elements, and insertion, deletion in a heap of size ‘K’ will take log(K) time. Hence, the overall time complexity is O(N * log(K)).

Accepted Answer

Quick Select

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.

Space Complexity: O(1)Explanation:

O(N), where ‘N’ denotes the number of elements present in the array.

In the worst-case quicksort partition algorithm’s recursive function stack can have ‘N’ elements. Hence, the overall space complexity is O(N).

Time Complexity: O(1)Explanation:

O(N + K*log(K)), where ‘N’ denotes the number of elements present in the array and ‘K’ is the count of the largest elements.

Finding Kth largest element using quicksort takes O(N) time and sorting the answer array of size ‘K’ takes K*log(K) time. Hence, the overall time complexity is O(N + K*log(K)).

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:

Output Format:

Note:

Follow Up:

Constraints:

Top Hike Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Hike Software Developer