# First Missing Positive problem solution (Leetcode)

First Missing Positive problem solution: Given an unsorted integer array `nums`, return the smallest missing positive integer.

You must implement an algorithm that runs in `O(n)` time and uses constant extra space.

Example 1:

```Input: nums = [1,2,0]
Output: 3
Explanation: The numbers in the range [1,2] are all in the array.
```

Example 2:

```Input: nums = [3,4,-1,1]
Output: 2
Explanation: 1 is in the array but 2 is missing.```

## Problem solution in Python

``````def firstMissingPositive(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
nums.sort()
if 1 not in nums:
return 1
a = nums.index(1)
for i in range(a+1, len(nums)):
if nums[i] - nums[i-1] > 1:
return nums[i-1] + 1
if i == len(nums)-1:
return nums[i] + 1
return 2
``````

## Problem solution in Java

``````class Solution {
public int firstMissingPositive(int[] nums) {
Set<Integer> set = new HashSet<>();

int first = 1;

for (int num : nums) {
if (num > 0) {
}

if (num == first) {
first++;

while (set.contains(first)) {
first++;
}
}
}

return first;
}
}
``````

## Problem solution in C++

``````int firstMissingPositive(vector<int> a) {

int i,n=a.size();
for(i=0;i<n;i++)
if(a[i]<=0 || a[i]>n)
a[i] = INT_MAX;

a.push_back(INT_MAX);
for(i=0;i<n;i++)
{
if(abs(a[i])==INT_MAX) continue;

if(a[abs(a[i])]>0)
a[abs(a[i])] *= -1;
}
for(i=1;i<=n;i++)
if(a[i]>0)
break;

return i;
}
``````

## Problem solution in C.

``````int firstMissingPositive(int* nums, int numsSize){
int i = 0;

while (i < numsSize)
{
int n = nums[i];

/* Swap nums[i] to nums[nums[i] - 1] if possible */
if (0 < n && n < (numsSize + 1) && (n - 1) != i && nums[n - 1] != n)
{
nums[i] = nums[n - 1];
nums[n - 1] = n;
}
else
{
i++;
}
}

for (i = 1; i < numsSize + 1; i++)
{
if (nums[i - 1] != i)
break;
}

return i;
}``````