Given an unordered list of N elements, write a function to find the top four elements of the given list. Make sure your function runs in linear time O(N).The solution is trivial for O(N log N), i.e. the optimal running time of comparison sort algorithms. It's not possible to sort the entire list any faster in a deterministic way. But because only the top four elements are required, we just need to identify the fourth largest element in O(N) time.
So, a selection algorithm. The fourth largest element can be found in linear time by partitioning the input list recursively, using the median of medians to identify optimal pivot points. I recall that this algorithm was taught in the early weeks of Algorithms, Part I -- and it's still the most surprising application of divide-and-conquer that I've seen so far.
Once the fourth largest element is identified, returning the top four elements follows immediately in linear time.
