Finding the minimum missing natural number - a better way! →
In one of the earlier posts we saw a straight forward way to find the minimum missing natural number in a list. That solution, although very straight forward, required us to sort the list before finding the minimum missing number. The question was - can we get away without that expense of sorting that list?
The answer seems to be yes. Since we know that we are not allowing any duplicates and we consider only natural numbers, we can use a very nice property:
In a perfectly consecutive sequence of natural numbers, any chosen number is also the number of natural numbers less than it.
That is, if we consider the consecutive sequence of number 0 1 2 3 4 5
and choose 3
, we see that there are exactly three natural numbers before it - 0 1 2
. A curious mind would have noted that these three numbers actually need not be in order - they should just exist. For example 1 0 2 3 4 5
has three numbers before 3
, they are not in sequence, but the fact that there are three of them assures us that nothing less than three is missing in the sequence. This is the property we are going to use to come up with a simpler search. Just like how we partitioned a list of numbers around a pivot element for quicksort, we will choose an element x
and push all the numbers less than it (in any order) to the left of it and the rest to the right of it. We will also need to keep track of the number of elements num
to the left of the chosen number (in order to check our fancy property mentioned above). Let’s write the partition function first:
If the number of elements tracked is equal to the chosen number, it just means that there is no missing number in the left partition (just like the example above where the number of elements less than 3
is equal to three, and we don’t have any missing natural number to the left of 3
). Now, we will use this partition function to find the missing natural number:
Think of m
as the accumulator - we know that 0
is the first natural number, so in case our input list is an empty one (base case), we just return the first (minimum) natural number that is missing. Is there too much going on in this? If you could work this out in a sample input, say [0; 3; 2; 9; 1]
it would help understand it better.