Algorithm to find k smallest numbers in array of n items

by

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.

More Related Contents:

  1. maximize the top element of the stack after performing exactly K operations
  2. Algorithm for all subsets of Array
  3. How to sort in-place using the merge sort algorithm?
  4. Easy interview question got harder: given numbers 1..100, find the missing number(s) given exactly k are missing
  5. Finding three elements in an array whose sum is closest to a given number
  6. Given an array of numbers, return array of products of all other numbers (no division)
  7. How to find the kth smallest element in the union of two sorted arrays?
  8. How do you efficiently generate a list of K non-repeating integers between 0 and an upper bound N [duplicate]
  9. Can min/max of moving window achieve in O(N)?
  10. Weighted random selection from array
  11. Print two-dimensional array in spiral order
  12. Find the Smallest Integer Not in a List
  13. How to find a duplicate element in an array of shuffled consecutive integers?
  14. Find the majority element in array
  15. How to divide a set into two subsets such that difference between the sum of numbers in two sets is minimal?
  16. Binary Search algorithm implementations
  17. Algorithm to determine if array contains n…n+m?
  18. Find the 2nd largest element in an array with minimum number of comparisons
  19. Find all subsets of length k in an array
  20. Maximum single-sell profit
  21. In-place array reordering?
  22. How to find max. and min. in array using minimum comparisons?
  23. Median of 5 sorted arrays
  24. find pair of numbers in array that add to given sum
  25. Regarding in-place merge in an array
  26. Interview question: three arrays and O(N*N)
  27. How to find repeating sequence of characters in a given array?
  28. Maximum sum of non consecutive elements
  29. Finding kth smallest number from n sorted arrays
  30. Algorithm to apply permutation in constant memory space

Leave a Comment