K'th smallest element in an array

Question

Given an array at the size of n give a deterministic algorithm (not quick sort) that uses O(1) space (not medians of medians) that will find the K'th smallest item.

There are the obvious solutions such as sorting the array on nlogn or finding the minimum k time in nk but I'm sure there is a better way of doing that. It doesn't have to be liner (I doubt it if it can).

Thanks for the helpers.

Answer 1

Arrange (so that no extra space is wasted) the array into a min-heap (can be built in O(n) time) and then do k extract-min operations, each of whicih takes O(log n) time. So you have O(n + k*log n) time altogether. (Since k <= n the worst case is O(n log n).)

The space complexity is O(1) or, if you count the array that we've modified, O(n); but any algorithm will need the array and will thus need those O(n) space contributed by the array. The additional space cost incurred by the heap is O(1).

It's obvious that this approach is correct: the first extract-min returns (and removes from the heap) the smallest element; the second extract-min returns (and removes from the heap) the second-smallest element; ...; and the k-th extract-min returns (and removes from the heap) the k-th smallest element.

If k is "much bigger" than n/2 then you can speed things up by using max-heap and search for (n-k)-th largest element using similar approach.