Given an array of integers find the kth element in the sorted order (not the kth distinct element). So, if the array is [3, 1, 2, 1, 4] and k is 3 then the result is 2, because it’s the 3rd element in sorted order (but the 3rd distinct element is 3).
This doesn’t sound as a very hard problem but I couldn’t find a solution better than:
– Sort using quicksort
– Return the element at index k
The complexity of this solution is the complexity of quicksort O(nlogn).