Find the minimum element missing from sequence of non-negative integers.

Question

I need to find the minimum missing element from a sequence of non-negative integers.

ex: I have: 0 5 10 4 3 1

The missing element is 2.

In above sequence missing elements are 2 6 7 8 9 . The minimum among them is 2 so answer is 2.

Brute force . I will sort the sequence and get the minimum element in nlogn .I am looking for better solution. Any help ?

Answer 1

Pseudocode:

for(int i = 0 ; i < Int.MAX ; i++)
{
   if(i is not in list)
   {
       return i
    }
}

Of course it may be possible to optimise this, but as an initial draft, in order to get your tests passing (you do have tests, right), its a very simple solution, which will give you confidence taht your tests are correct, freeing you up to optimise if needed.

Answer 2

No need for sorting.

1. Go over the list and find the 2 smallest valuse, which the difference between them is bigger than 1. (O(N)).

2. Print the (least value was found)+1.

Answer 3

1. Sort the array (O(NlogN) worst-case for mergesort)
2. Loop from the beginning, until a difference of more than 1 between two adjacent elements is encountered. (O(N) worst-case)

Answer 4

Simplest approach I can think of is to sort the list and then look through it for the first gap.

I'm not sure there's anything much simpler. Even if you parse the list somehow without actually sorting it you're going to need to keep track of the gaps you've found along the way and then eliminate them as you go. I think it's probably logically equivalent to a sort algorithm anyway. Could be wrong.

Answer 5

First sort the elements. Then start finding the numbers in your sequence like:

for (int i=0; i<numbers.length; i++) {
   if (numbers[i] != i ) {
       System.out.println("Missing number is: " + i); break;
   }
}

Answer 6

Can be done in O(n) with a hash table, which means O(n) additional memory:

1. Insert the numbers to a hash table, done in O(n).
2. Go from zero to the list's maximum, and check whether the number exists. The first number that does not exist is the answer. This is also done in O(n).

Answer 7

Pseudocode :

a is the array
s is a sorted set (examples : a binary search tree, or a red/black tree)

insert 0 in s
for each v in a
  remove v from s
  insert v+1 in s

result is min(s)

Answer 8

If you know there are no repeated elements you can do in O(N log N) time with O(1) memory:

You do a binary search to find the answer: initially you know the answer is between 0 and N-1, for each step, you count how many numbers are less than k (k the middle element of the binary search segment), if this number is equal to k, then that part of the sequence is complete, so you need to search the upper part, otherwise you need to search the lower part.

Answer 9

In ISO C99:

unsigned least_absent(unsigned seq_sz, unsigned seq[seq_sz])
{
   bool tab[seq_sz];
   memset(tab, 0, sizeof(tab));
   for(unsigned i=0; i<seq_sz; i++)
      if(seq[i] < seq_sz)
         tab[seq[i]] = true;
   for(unsigned i=0; i<seq_sz; i++)
      if(!tab[i])
         return i;
   return seq_sz;
}

This is O(n) time, O(n) memory.

Answer 10

list = sort(list)
last_element = list[0]
for(i = 1; i < list.size; ++i){
   if(list[i] - last_element > 1) 
      return last_element + 1 // return the next number after last_element
   last_element = list[i]
}
return -1 // return -1 if unable to find a number

Answer 11

Improving some of the ideas (@Faisal Feroz, @slacker, @dahunter, @user453201): During the pass on the values list (Sorting, or inserting the values to hash/ lookup table), save the minimum. Then, in order to find the missing element, start from this minimum instead of 0. Small improvement, but it's still better.