Given n integers and a number k, you are asked to find the k-th smallest element in the list. Itβs guaranteed that the array elements are distinct.
Input
The first line of the input contains two integers n and k (1 β€ k β€ n β€ ).
The next line contains n space-separated integers ().
Output
The program should output the value of the k-th smallest element in the given list.
Examples
Input
Output
6 3
10 -2 4 8 3 6
4
7 2
-4 5 8 -3 10 0 7
-3
Explanation
The sorted list would be [-2, 3, 4, 6, 8, 10] β the 3rd smallest element would be 4
The sorted list would be [-4, -3, 0, 5, 7, 8, 10] β the 2nd smallest would be -3
Β
Hint 1
Use random partitioning similar to QuickSort.
Sorting elements is not viable under this time-limit constraint.
Hint 2
You can partition the array similar to QuickSort with a randomly chosen pivot. After which, you can keep only the part of the array thatβs needed and ignore the other part.
This process can be repeated until the number of ignored elements BEFORE your current item is equal to k.
Random partitioning will actually have an expected linear time . Do you know why?
Hint 3
Each time we randomly partition the array, the expected size of the resulting array is half the current one. So, if the current array has a size of n, after one partitioning we can throw away half of it - n/2, after two partitioning operations, we can throw away the other half - n/4, and so on. So, this sum becomes .
Yet, the algorithm can have a worst-case performance in case the randomly chosen elements donβt partition the array into an expected n/2 size.