Multi tool use

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

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

ex: I have: 0 5 10 4 3 1

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 ?

12 Answers
12

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.

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

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


This solution is O(n) space and time complexity.

def solution(A):
#Python 3.6

a = set() #to store positive numbers in the given array
b = set() #to store missing positive numbers in the given array

for item in A:
if item<=0:
continue
a.add(item)
if item in b:
b.remove(item)
if item + 1 not in a:
b.add(item+1)

#if all numbers are negative in the given array
if len(a) == 0:
return 1

#if 1 is not in the given array, 1 is the answer
if 1 not in a:
return 1

return min(b)


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.

No need for sorting.

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

Print the (least value was found)+1.

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.

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;
}
}


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)


O(NlogN)

O(N)

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.

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.

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.