Given an array of integers, what algorithm will return the sum of the five smallest numbers? I want to do this with a single pass and without relying on a sorting algorithm.
Given that we can not just sort the input array and get the five smallest numbers, I was planning to store the first five numbers at the beginning and then compare the rest of the inputs and keep storing the five smallest numbers. But how do I pick up the first smallest five without a sorting algorithm?
You can use the selection algorithm, where k is 5. You can them return the list from the beginning to k and sum all of the numbers. It is O(n) if you do median of medians.
This algorithm relies on the same partition routine that some sorts rely on (think quicksort). It does not, however, sort the elements.
Traverse the array and put the elements in a max heap of size 5. So finally the elements present in the max heap are the smallest elements and their sum would result in the required answer.
For each element (say x) in the array check if it smaller than the max element in the max heap .
If it is small then replace the max element from the heap with x.
Else just go to the next element.
Finally you will have only the 5 smallest elements in the heap.
Picking the initial five numbers does not require you to pick the five smallest numbers before looking at the rest of the array: if you did, you wouldn't need to look through the rest of the array.
Let's simplify this by writing a signature for your method:
getSmallest(array<int> input, int nSmallest) -> array<int> # length of nSmallest
What does this method have to do?
nSmallest elements into the output arrayThe resulting output array will hold all the elements which are smallest, and nothing will have been sorted. Let's write some pseudocode, starting with the check against the output array:
# returns true if the candidate was swapped in, false otherwise.
# NOTE: outputArray and candidate can be modified by this function!
# If boolean is 'true' then 'candidate' will contain the swapped out element
swapElement(array<int> outputArray, int candidate) -> boolean
foreach idx->smallNumber in outputArray
if (candidate < smallNumber) {
outputArray[idx] = candidate
candidate = smallNumber
return true
}
return false
Now that we've handled this core problem, how do we use the solution?
getSmallest(array<int> input, int nSmallest) -> array<int>
output[nSmallest] = copy(input, nSmallest) # copies the first nSmallest elements into output
# Iterate through the remainder of the list
for (idx = nSmallest, length(input), idx++) {
checkingCandidate = true
candidate = input[idx]
while (checkingCandidate){ # This ensures that swapped candidates get checked too, no matter how many
checkingCandidate = swapElement(output, candidate)
} # This will quit once we are no longer swapping elements.
}
return output
And there you have your complete solution - in pseudocode. As you can see, the core problem is having your output array, and swapping in the smaller element as you find it (preventing you from needing to sort the array first). Once you reduce the problem to 'is x element smaller than anything in y array', the rest is just iteration. Oh, and at the end you just add all the numbers in your output array - which should be trivial.
You can use priority queue which has size of 5. The compared function is to keep the biggest number to the head.
When it iterates the array, push num to the queue if size < 5, and compare the head num of the queue with the rest nums if size = 5. if array[i] < queue.front(), then pop head of the queue, and push array[i] into the queue.
at last, sum of the queue is the smallest.
