K Largest Elements

Problem Statement :

You are given with an integer k and an array of integers that contain numbers in random order. Write a program to find k largest numbers from given array. You need to save them in an array and return it.

Order of elements in the output is not important.

Input Format :

Line 1 : Size of array (n)
Line 2 : Array elements (separated by space)
Line 3 : Integer k

Output Format :

k largest elements

Sample Input :

13
2 12 9 16 10 5 3 20 25 11 1 8 6 
4

Sample Output :

12
16
20
25

Explanation of Test Case:

Here we obtain the 4 largest elements from array of size 13.

Approach:

We solve this problem using priority queues. Insert k elements in priority queue. Then, for the remaining elements, compare them with the max of the priority queue kept at top. If the current element is greater than top of priority queue, then pop the first element of priority queue and push the current element inside it. Since the return type of question is vector, so convert heap into vector.

Time complexity — O(n * logk)

Space complexity — O(k)

Code:

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.