First Missing Integer

Last updated: 29th Aug, 2020

Problem Statment

Given an unsorted integer array, find the first missing positive integer.

Example 1:

[1,2,0]

>> 3

Approach:

Sort the vector array and take a key variable as 1. If the array element is greater than key then the first missing positive integer is key and if the the array element is equal to key then increment the key by 1 and find the first missing positive integer.

Time and Space Complexity :
Time - O(n)
Space - O(n)

Pseudocode :
sort(a)
for(i=0 to n)
   if(a[i]>0)
    if(a[i]>key)
     key
    else if(a[i]==key)
     key++

C++ Code

void missing_integer(vector<int>a)
{
	int key=1,k;
	sort(a.begin(),a.end());
	for(int i=0;i<a.size();i++)
	{
		if(a[i]>0)
		{
			if(a[i]>key)
			  k=key;
			else if(a[i]==key)
				k=key++;

		}
	}
	cout<<k;
}