Fastest way to find smallest missing integer from list of integers

Question

I have a list of 100 random integers. Each random integer has a value from 0 to 99. Duplicates are allowed, so the list could be something like

56, 1, 1, 1, 1, 0, 2, 6, 99...

I need to find the smallest integer (>= 0) is that is not contained in the list.

My initial solution is this:

vector<int> integerList(100); //list of random integers
...
vector<bool> listedIntegers(101, false);
for (int theInt : integerList)
{
    listedIntegers[theInt] = true;
}
int smallestInt;
for (int j = 0; j < 101; j++)
{
    if (!listedIntegers[j])
    {
        smallestInt = j;
        break;
    }
}

But that requires a secondary array for book-keeping and a second (potentially full) list iteration. I need to perform this task millions of times (the actual application is in a greedy graph coloring algorithm, where I need to find the smallest unused color value with a vertex adjacency list), so I'm wondering if there's a clever way to get the same result without so much overhead?

Answer 1

It's been a year, but ...

One idea that comes to mind is to keep track of the interval(s) of unused values as you iterate the list. To allow efficient lookup, you could keep intervals as tuples in a binary search tree, for example.

So, using your sample data:

56, 1, 1, 1, 1, 0, 2, 6, 99...

You would initially have the unused interval [0..99], and then, as each input value is processed:

56: [0..55][57..99]
1: [0..0][2..55][57..99]
1: no change
1: no change
1: no change
0: [2..55][57..99]
2: [3..55][57..99]
6: [3..5][7..55][57..99]
99: [3..5][7..55][57..98]

Result (lowest value in lowest remaining interval): 3