Find First Missing Number

Given an array of integers, find the first missing positive integer in linear time and constant space. In other words, find the lowest positive integer that does not exist in the array. The array can contain duplicates and negative numbers as well.

Example:

Input:  arr[]={3,4,-1,1}
Output: 2

Approach 1: Using Memory

C++

#include <bits/stdc++.h>
using namespace std;

int firstMissingPositive(vector<int> &nums)
{
    set<int> st;

    //insert positive number into the set
    for (int i = 0; i < nums.size(); i++)
    {
        if (nums[i] > 0)
        {
            st.insert(nums[i]);
        }
    }
    int ans;
    for (int i = 1;; i++)
    {
        //if missing number found then break
        if (st.find(i) == st.end())
        {
            ans = i;
            break;
        }
    }
    return ans;
}
int main()
{
    vector<int> arr = {3, 4, -1, 1};

    cout << firstMissingPositive(arr);

    return 0;
}

//Time Compplexity :O(maximum element in the array)
//Space Complexity: O(n)

Approach 2:

C++

#include <bits/stdc++.h>
using namespace std;

int firstMissingPositive(vector<int> &nums)
{
    int n = nums.size();
    for (int i = 0; i < n; i++)
    {
        //if negative then continue to
        //next index
        if (nums[i] < 0)
        {
            continue;
        }
        int pos = nums[i] - 1;
        while (pos != i)
        {
            if (pos < 0 || pos >= n || nums[pos] == nums[i])
                break;
            swap(nums[i], nums[pos]);
            pos = nums[i] - 1;
        }
    }
    int i = 0;
    for (i = 0; i < n; i++)
    {
        if (nums[i] - 1 != i)
        {
            return i + 1;
        }
    }
    return i + 1;
}
int main()
{
    vector<int> arr = {3, 4, -1, 1};

    cout << firstMissingPositive(arr);

    return 0;
}

//Time Compplexity :O(n)
//Space Complexity :O(1)