I came across this interesting problem on typeocaml.com web site:

Given a unordered list of distinct natural numbers, find out the minimum natural number that is not in the list.
For example, if the list is [8; 2; 3; 0; 12; 4; 1; 6], then 5 is the minimum natural number that is missing.
O(n) solution is desired.

The solution provided on the web page has a complexity of O(n) in the average case as mentioned in the article. However the worst case complexity is O(n^2) if the randomly picked number is always the next smallest (or largest) number.

Here I describe my solution with a similar (?) complexity. My algorithm generates a list of ranges as the numbers are read. Every range has a minimum and a maximum value of the contiguous numbers that were not seen so far at the input. The list of ranges is updated and kept sorted for each input element. The solution is the lower bound in the first range element after all inputs are consumed.

First step is to initialize the range list with a single range element with lower bound being zero and upper bound being the first input less one. If the input array contains only one element, then the list contains one range, and the solution is the lower bound in that range, i.e zero.

For the rest of the input, if the next element e is:

  • equal to the upper bound of an existing range (l, u), update that range with (l, e-1).
  • equal to the lower bound of an existing range (l, u), update that range with (e+1, u).
  • equal to an existing range with identical upper and lower bounds (e,e), remove the range from the list.
  • inside an existing range (l, u), split that range into two: (l, e-1) and (e+1, u)
  • larger than the entire range list, add a new range (e, e) at the end of the list.

Here is how the algorithm works on the input array {8, 2, 3, 0, 12, 4, 1, 6} mentioned in the article:

e  L
8  (0,7)                  Initialize the list
2  (0,1) (3,7)            e in 1st range, split
3  (0,1) (4,7)            e in 2nd range, update lower bound
0  (1,1) (4,7)            e in 1st range, update lower bound
12 (1,1) (4,7) (12,12)    e larger than list, add range
4  (1,1) (5,7) (12,12)    e in 2nd range, update lower bound
1  (5,7) (12,12)          e equal to 1st range, remove
6  (5,5) (7,7) (12,12)    e in 1st range, split

The answer is the lower bound of the first range, i.e. 5.

At every step a new range can be added, removed or the list size doesn’t change. On the average the number of the ranges is nearly constant which gives a complexity of O(n).

In the worst case a new range is added at each step which gives a complexity of O(n^2).

A detailed complexity analysis or any type of comment is greatly appreciated.

 


No Comments to “The Min Missing Natural Number – Another Solution”  

  1. No Comments

Leave a Reply