243. The Kth Smallest Value
Foundation1000 ms256 MBSolved by 0%
Print the kth smallest of n integers, counting from 1. So k = 1 is
the minimum.
Duplicates count as separate values. In 2 2 2, the 2nd smallest is 2.
The direct approach is to sort and read position k - 1. That is O(n log n)
and entirely acceptable here. It is worth knowing that a selection algorithm
can do it in O(n) on average without fully sorting, which matters when n
is enormous and k is small.
Constraints - `1 ≤ k ≤ n ≤ 200000` - `-1000000000 ≤ a[i] ≤ 1000000000`
Input
The first line contains two integers n and k.
The second line contains n integers in any order.
Output
Print one integer, the kth smallest value.
Input3 1
3 1 2
Output1
Noteasks for the smallest, which is not the first element given
Input3 3
3 1 2
Output3
Noteasks for the largest
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.
Hint 1Where to start
Hint 2The approachOpen hint 1 first. This one carries on from it.
Hint 3PseudocodeOpen hint 2 first. This one carries on from it.
Hint 4Full solutionOpen hint 3 first. This one carries on from it.