Iteration
K Smallest Elements
Given an array arr and an integer k, return the k smallest elements in the array. Note that "elements" is plural.
You can return the elements in any order, and 0 < k <= len(arr).
The standard interview solution is to add all the elements to a Heap, and then pop the Heap k times. Every time you pop an element, you add it to the answer, since it's one of the k smallest elements.
Here's the code:
Time Complexity O(n+klogn). Turning the array into a heap takes O(n) time. We then pop from the heap k times, and each pop takes logn time.
Space Complexity O(1). You don't end up using any extra space in the above solution. You're just transferring elements from arr into answer.
That was the standard interview solution, but it's actually not optimal. Here's the optimal solution, which probably isn't needed for an interview. It uses QuickSelect and takes O(n) time.
In the last problem, we saw that QuickSelect lets you find the kth smallest element in O(n) time.
It turns out QuickSelect also lets you find the k smallest elements in O(n) time. All you need to do is find the kth smallest element, and then iterate through the array again and find all the elements less than it.
Time Complexity O(n). Finding the kth smallest element using QuickSelect takes O(n) time on average. After we find it, we iterate through all the numbers again, which takes O(n) time.
Space Complexity O(k) for the output array.
A 3rd solution is to use Counting Sort to sort the elements and then take the top k, but the stars really need to align for it to be optimal, and it's advanced knowledge. Counting Sort only works in certain problems, and it takes O(n+max−min) time in general. It's only O(n) if you know the range of elements is O(n) too, like counting the top frequencies of elements in an array.
