K Smallest 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 smallest numbers from given array. You need to save them in an array and return it.

Note: Order of elements in the output is not important.

Input Format :

The first line of input contains an integer, that denotes the value of the size of the array. Let us denote it with the symbol N.
The following line contains N space separated integers, that denote the value of the elements of the array.
The following line contains an integer, that denotes the value of k.

Output Format :

The first and only line of output print k smallest elements. The elements in the output are separated by a single space.

Sample Input:

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

Sample Output:

1 2 3 5

Explanation of Test Case:

Here we obtain the 4 smallest 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 min of the priority queue kept at top. If the current element is smaller 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.