The problem is to find out the smallest missing positive integer given an unsorted integer array. We can solve this problem in linear time O(N) and in constant time O(1) using a greedy approach with hash map.

We have explored 3 approaches to solve this:

• Brute force approach O(N^2) time and O(1) space
• Sorting approach O(N logN) time and O(1) space
• Greedy approach O(N) time and O(1) space

Example :

Input: [7,8,9,11,12]
Expected Output : 1

Another example:

Input: [-1, -10, 3, 99, 0, 1, 2, 5]
Expected output: 4

Note 0 is not a positive integer.

Brute force approach

Traverse the array multiple times and find the next smallest integer each time.
If the minimum found in the before traversal and the min found in the current traversal aren't consecutive positive integers, return 1+the min of previous traversal.

Steps:

• Define minimum = 1 and current_minimum = 0
• Find the smallest number greater than current_minimum and update it
• If minimum >= current_minimum, then increment minimum by 1 and go to the previous step
• If minimum < current_minimum, then answer is minimum

The second step takes O(N) time so the worst case time complexity is O(N^2) time. The space complexity is constant O(1).

Following is the C++ function implementation of the above approach:

int firstMissingPositive(vector<int>& nums) 
{
    int minnum=1;
    int currmin=INT_MAX;
    int i=0,j,minind;
    while(i<nums.size())
    {
        for(j=0;j<nums.size();j++)
        {
            if(nums[i]>0 && currmin>nums[j])
            {
                currmin=nums[j];
                minind=j;
            }
        }
        if(currmin!=minnum)
        {
            return minnum;
        }
        nums[minind]=-1;
        minnum+=1;
        i++;
    }
    return minnum;
}

The complexity of above method would be O(n^2).

Better approach (using sorting)

Sort the array and then find the missing smallest positve integer by traversing from the beginning.

Following is the C++ function implementation of the above approach:

int firstMissingPositive(vector<int>& nums) 
{
    sort(nums.begin(),nums.end());
    int exp=1;
    for(int i=0;i<nums.size();i++)
    {
        if(nums[i]<=0)
            continue;
        if(nums[i]==exp)
            exp++;
        else return exp;
    }
    return exp;
    }

The complexity of above method would be O(nlogn).

Best approach (using Hashmap)

The best approach for solving this problem would be to use a map for storing the positve numbers in the array and their frequencies and then, traverse the map starting with the smallest number and checking if it exists in the map.

Steps:

• If the first element in the map doesn't have key as 1, we return 1 as the missing positive integer.
• The variable prev keeps track of last found positive integer.
• We then traverse the map.
• If the current element isn't one more than prev, then one more than prev is missing from the array. We return it.
• Else increment prev.

The complexity of above approach is O(N) and works well when the distribution of the input elements are widely spread.

Following is the C++ function implementation of the above approach:

int firstMissingPositive(vector<int>& nums) {
    map<int,int> m;
    for(int i=0;i<nums.size();i++)
        if(nums[i]>=0)
            m[nums[i]]++;
    if(m.begin()->first!=1)
        return 1;
    int prev=1;
    map<int,int> :: iterator itr;
    for(itr=m.begin();itr!=m.end();itr++){
        if(itr->first!=prev)
            return prev;
        prev+=1;
    }
    return prev;  
}

This can be implemented without using iterator as well. The pseudocode of the approach will be as follows:

list
count = 0
for i from 0 to length(list):
    if list[i] exists in map
        increment value of list[i] in map by 1
    else
        Add list[i] in map and value 1
        ++ count
    
minimum = 1
while(count > 0)
    if minimum is in map:
        increment minimum by 1
        decrease count by 1
    else
        return minimum

This can be seen as a greedy approach as we are starting with the minimum number and checking if it is the answer.

The above approach runs in O(N) time and uses constant extra space.

Example 1:

Input: [1,2,0]
Output: 3

Example 2:

Input: [3,4,-1,1]
Output: 2

This question is related to the topic of Arrays. If you aren't sure about it, I suggest you first learn Arrays and then come back and try solving this problem.

P.S.We do not care about duplicates and non-positive numbers in the above question.

With this article at OpenGenus, you must have the complete idea of solving this problem of finding the smallest missing positive integer efficiently.