# First Missing Non Negative Integer

Last updated: 17th Jan, 2021

#### Problem Statment

Given an unsorted integer array, find the first missing non negative integer.
Example 1:
[1,2,0]
>> 3

Approach 1:

The bruteforce approach for such a problem involves, sorting the given array.
After sorting, iterate over the array of length 'n'. For each i:0->n-1, if array[i]!=i, then the current value of i, is the first missing non negative integer and can be returned. If the array is iterated and for all valid i(0->n-1), array[i]=i, the first missing non negative integer is n.
Time and Space Complexity :
Time - O(nlogn)
Space - O(1)

###### C++ Code

    void missing_integer(vector<int>a)
    {
    	sort(a.begin(),a.end());
    	for(int i=0;i<a.size();i++){
        if(a[i]!=i){
          cout<<i<<'\n';
          return;
          }
        }
    	cout<< a.size()<<'\n';
    }

Approach 2:

This solution can be further optimised.
The basic idea is for any n non negative numbers, the first missing non negative number must be within [0,n]. The reasoning is similar to putting k balls into k+1 bins, there must be a bin empty, the empty bin can be viewed as the missing number.
Time and Space Complexity :
Time - O(n)
Space - O(1)

###### C++ Code

    void missing_integer(vector<int>a)
    {
      int n = a.size();
      for(int i=0;i<n;i++){
        while(a[i]>=0 && a[i]<n && a[a[i]]!=a[i]){
          //Elements in array can vary from 0 to n-1
          //An array of size n has indixes varying from 0 to n-1 too
          //Place element with value i, at index i
          swap(a[i], a[a[i]]);
          }
      }
      for(int i=0;i<n;i++){
        if(a[i]!=i){
          cout<<i<<'\n';
          return;
        }
      }
      cout<< a.size()<<'\n';
    }