Algorithm to find k smallest numbers in array of n items

arrays algorithm selection
Jessica picture Jessica · Mar 21, 2011 · Viewed 66.5k times · Source

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

Chet picture Chet · Oct 6, 2011

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.

Related questions

How do I check if an array includes a value in JavaScript?

What is the most concise and efficient way to find out if a JavaScript array contains a value? This is the only way I know to do it: function contains(a, obj) { for (var i = 0; i < a.length; i++) { …

Read More
Finding the max/min value in an array of primitives using Java

It's trivial to write a function to determine the min/max value in an array, such as: /** * * @param chars * @return the max value in the array of chars */ private static int maxValue(char[] chars) { int max = chars[0]; for (int ktr = 0; …

Read More
Java, Shifting Elements in an Array

I have an array of objects in Java, and I am trying to pull one element to the top and shift the rest down by one. Assume I have an array of size 10, and I am trying to pull the …

Read More