[Solved] How to find the minimal missing integer in a list in an STL way

by


You can do this by building a set of integers and adding larger seen in the set, and holding the minimum not seen in as a counter. Once there is a number that is equal to the latter, go through the set removing elements until there is a missing integer.

Please see below for implementation.

template<typename I> typename I::value_type solver(I b, I e)
{
    constexpr typename I::value_type maxseen=
      std::numeric_limits<typename I::value_type>::max();
    std::set<typename I::value_type> seen{maxseen};

    typename I::value_type minnotseen(1);

    for(I p=b; p!=e;++p)
    {
        if(*p == minnotseen)
        {
            while(++minnotseen == *seen.begin())
            {
                seen.erase(seen.begin());
            }

        } else if( *p > minnotseen)
        {
            seen.insert(*p);
        }
    }

    return minnotseen;
}

In case you sequence is in a vector you should use this with:

solver(sequence.begin(),sequence.end());

The algorithm is O(N) in time and O(1) in space since it uses only a counter, constant size additional space, and a few iterators to keep track of the least value.

Complexity ( order of growth rate ) The algorithm keeps a subset only of the input which is expected to be of constant order of growth with respect the growth rate of the input, thus O(1) in space. The growth rate of the iterations is O(N+NlogK) where K is the growth rate of the larger subsequence of seen larger numbers. The latter is the aforementioned subsequence of constant growth rate i.e. K=1 , which results in the algorithm having O(N) complexity. (see comments)

17

solved How to find the minimal missing integer in a list in an STL way