Finding the lowest missing integer in a vector containing positive and negative int's?

Question

I'm writing an operation to find the lowest missing element of a vector, V = 1..N + 1. This has to be performed in O(N) time complexity.

Solution One:

std::vector<int> A {3,4,1,4,6,7};

int main()
{
    int max_el = *std::max_element(A.begin(), A.end()); //Find max element
    std::vector<int> V(max_el);
    std::iota(V.begin(), V.end(), 1) //Populate V with all int's up to max element

    for(unsigned into i {0}; i < A.size(); i++)
    {
       int index = A[i] - 1;
       if(A[i] == V[index]) //Search V in O(1)
       {
         V[index] = max_el; //Set each to max_el, leaving the missing int 
       }
    }
    return *std::min_element(V.begin(), V.end()); //Find missing int as its the lowest (hasn't been set to max_el)
}

//Output: 2

This works completely fine.

However, I'm now trying to get this to work with vector containing negative int's.

Solution Two:

My logic is to take the same approach, however 'weight' the indexes given the size of the vector and the number of negative int's in the vector:

std::vector<int> A {-1, -4, -2, 0, 3, 2, 1}
int main()
{
   int max_el = *std::max_element(A.begin(), A.end());
   int min_el = *std::min_element(A.begin(), A.end());
   int min_el_abs = abs(min_el); //Convert min element to absolute
   int total = min_el_abs + max_el;

   std::vector<int> V(total + 1);
   std::iota(V.begin(), V.end(), min_el);
   int index;

   //Find amount of negative int's
   int first_pos;
   for(unsigned int i {0}; i < A.size(); i++)
   {
      if(A[i] >= 0) {first_pos = i; break;}
   }

   for(unsigned int i {0}; i < A.size(); i++)
   {
      if(A[i] <= 0) //If negative
      {
          index = (A.size() - first_pos) - abs(A[i]);
       } else 
       {
          index = (A[i] + 1) + first_pos;
       }
       if(A[i] == V[index])
       {
          V[index] = 0;
       }
    } 
    return *std::min_element(V.begin(), V.end());
 } 

 //Output: -3

Solution Two fails to compare the values of the two vectors (A and V), as calculating the index with the above methods with a positive int doesn't work.

1) How can I get my Solution 2 to work with unordered vector's of negative int's?

2) How can I edit my Solution 2 to work with vectors of positive as well as vectors with negative int's?

Answer 1

Your first solution seems O(max(N,M)), where I consider N the number of elements in vector A and M the size of vector V (or max(A_i)), but you are looping through both vectors multiple times (with std::min_element, std::max_element, the for loop, the allocation of V and std::iota too).

Besides, once corrected a couple of typos (a missing ; and an into instead of int), your program returns the value found... from main(), which is a bit odd.

Your first algorithm always searches for the lowest missing value in the range [1, max value in A], but it can be generalized to find the lowest missing element in the range [min(A_i), max(A_i)], even for negative numbers.

My approach is similar to that of L.Senioins, but I've used different library functions trying to minimize the number of loops.

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>

template <class ForwardIt>
typename std::iterator_traits<ForwardIt>::value_type
lowest_missing(ForwardIt first, ForwardIt last)
{
    if ( first == last )
        throw std::string {"The range is empty"};
    // find both min and max element with one function
    auto result = std::minmax_element(first, last);

    // range is always > 0  
    auto range = *result.second - *result.first + 1;
    if ( range < 2 )
        throw std::string {"Min equals max, so there are no missing elements"};
    std::vector<bool> vb(range); // the initial value of all elements is false

    for (auto i = first; i != last; ++i)
        vb[*i - *result.first] = true;

    // search the first false
    auto pos = std::find(vb.cbegin(), vb.cend(), false);
    if ( pos == vb.cend() )  // all the elements are true
        throw std::string {"There are no missing elements"};

    return std::distance(vb.cbegin(), pos) + *result.first;
}

template <class ForwardIt>
void show_the_first_missing_element(ForwardIt first, ForwardIt last)
{
    try
    {
        std::cout << lowest_missing(first, last) << '\n';
    }
    catch(const std::string &msg)
    {
        std::cout << msg << '\n';
    }
}

int main() {
    std::vector<int> a { 1, 8, 9, 6, 2, 5, 3, 0 };
    show_the_first_missing_element(a.cbegin(), a.cend());

    std::vector<int> b { -1, -4, 8, 1, -3, -2, 10, 0 };
    show_the_first_missing_element(b.cbegin(), b.cend());
    show_the_first_missing_element(b.cbegin() + b.size() / 2, b.cend());

    std::vector<int> c { -2, -1, 0, 1, 2, 3 };
    show_the_first_missing_element(c.cbegin(), c.cend());

    std::vector<int> d { 3, 3, 3 };
    show_the_first_missing_element(d.cbegin(), d.cend());

    std::vector<int> e;
    show_the_first_missing_element(e.cbegin(), e.cend());

    return 0;
}

The results outputted for my test cases are:

4
2
-1
There are no missing elements
Min equals max, so there are no missing elements
The range is empty

Answer 2

My solution is to make a bool vector (or char vector just to avoid compilation warnings about casting to bool) which has the size of all possible elements. All elements are initialized to 0 and later are assigned to 1 which indicates that the element is not missing. All you need to do then is to find an index of the first 0 element which is the lowest missing element.

#include <vector>
#include <algorithm>
#include <iostream>

std::vector<int> A{ -1, 0, 11, 1, 10, -5 };

int main() {
    if (A.size() > 1) {
        int max_el = *std::max_element(A.begin(), A.end());
        int min_el = *std::min_element(A.begin(), A.end());
        int range = abs(max_el - min_el) + 1;

        std::vector<int> V(range, 0);

        for (size_t i = 0; i < A.size(); i++)
            V[A[i] - min_el] = 1;

        if (*std::min_element(V.begin(), V.end()) == 0)
            std::cout << std::distance(V.begin(), std::find(V.begin(), V.end(), 0)) + min_el;
        else
            std::cout << "There are no missing elements" << std::endl;
    }
    else
        std::cout << "There are no missing elements" << std::endl;

    std::cin.get();
}