Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Last Updated: 21 Nov, 2020

Easy

```
If 'N' is 5 and 'K' is 3 and the array is 7, 2, 6, 1, 9
Sorting the array we get 1, 2, 6, 7, 9
Hence the 3rd smallest number is 6.
```

```
The first line contains two space-separated integers ‘N’ representing the size of the array and ‘K’.
The second line contains 'N' space-separated integers that represent elements of the array 'ARR'.
```

```
Print a single line that contains a single integer which is the 'Kth' smallest element of the array.
```

```
You do not need to print anything; it has already been taken care of. Just implement the given function.
```

- Sort the elements of ‘ARR’ using function ‘SORT’
- Return element at ('K' - 1)th index

- We’ll use min heaps to store the elements of 'ARR' and perform 'K' GETMIN operations to get Kth minimum element.
- We’ll create an empty heap MINHEAP.
- We’ll add 'ARR'['I'] to MINHEAP for each 0 <= 'I' < 'N'. Every time the element is added the structure will HEAPIFY itself, such that the minimum element is always at the root node of the heap.
- Call GETMIN function 'K' times and store the result in 'KTHMIN' variable.
- Return 'KTHMIN'.

We’ll use a max heap of fixed size 'K' to store the elements of 'ARR' and perform a single 'GETMAX' operation to get 'K'th minimum element.

- We’ll create an empty heap 'MAXHEAP'.
- We’ll add 'ARR'['I'] to 'MAXHEAP' for each 0 <= 'I' < 'K'. Every time the element is added the structure will HEAPIFY itself, such that the maximum element is always at the root node of the heap.
- For each 'I' where, 'K' <= 'I' <= N, If 'ARR'['I'] < 'MAXHEAP'.'GETMAX'
- Replace ROOT of 'MAXHEAP' by 'ARR'['I'] .
- HEAPIFY the 'MAXHEAP'.

- Call 'GETMAX' and store its value in 'KTHMIN'.
- Return 'KTHMIN'.