Algorithm to find k smallest numbers in array of n items

Question

I'm trying to write an algorithm which can print the k smallest numbers in an n-size-array in O(n) time, but I cannot reduce the time complexity to n. How can I do this?

Answer 1

I've done this in an interview before, and one of the most elegant/efficient ways to do this is

O(n log k).  with space: O(k) (thanks, @Nzbuu) 

Basically you're going to use a max-heap of size limited to k. For each item in the array, check to see if it's smaller than the max (only O(1)). If it is, remove the max and put that in the heap (O(log k)). If its bigger, go to the next item.

Of course, the heap doesn't yield a sorted list of k items, but that can be done in O(k log k) which is easy.

Similarly, you can do the same for finding the largest k items, in which case you would use a min-heap.

Answer 2

you will need to find the k'th smallest element using 'selection algorithm', which is O(n), and then iterate the array again and return each element which is smaller/equals it.
selection algorithm: http://en.wikipedia.org/wiki/Selection_algorithm
you will have to pay attention if you have repeats: you will need to make sure you are not returning more then k elements (it is possible if for instance you have 1,2,...,k,k,k,...)

EDIT :
the full algorithm, and returning a list, as requested: let the array be A

 1. find the k'th element in A using 'selection algorithm', let it be 'z'  2. initialize an empty list 'L'  3. initialize counter<-0  4. for each element in A:   4.1. if element < z:     4.1.1. counter<-counter + 1 ; L.add(element)  5. for each element in A:  5.1. if element == z AND count < k:    5.1.1. counter<-counter + 1 ; L.add(element)  6. return L 

note here that a 3rd iteration is required if your list might have duplicates. if it can't - it is needless, just change the condition in 4.1 to <=.
also note: L.add is inserting an element to a linked list and thus is O(1).