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

I'm going to try give my own question an answer, after spending sometime thinking about this:

int main()
{
  std::vector<int> A {-3, -1, 0, 1, 3, 4};
  auto relative_pos = std::minmax_elment(A.begin(), A.end());
  std::vector<bool> Litmus( *(relative_pos.second) - *(relative_pos.first), false); //Create vector of size max val - min val)

  auto lowest_val = *(relative_pos.first);
  for(auto x : A)
  {
     Litmus[i - lowest_val] = true;
  }
  auto pos = std::find(Litmus.begin(), Litmus.end(), false); //Find the first occurring false value
  std::cout<< (pos - Litmus.begin()) + lower<<std::endl; //Print the val in A relative to false value in Litmus
}

This solution works with negative numbers and is linear.