# First missing positive

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

**Example 2:**

**Input:** nums = [3,4,-1,1]

**Output:** 2

**Example 3:**

**Input:** nums = [7,8,9,11,12]

**Output:** 1

**Constraints:**

`1 <= nums.length <= 5 * 105`

`-2^31 <= nums[i] <= 2^31 - 1`

Approach 1:

Run a loop from 1 to len(nums)+1 including both . Then for each time , check if the number is present in the nums array or not .

`loop from 1 to length of nums+1:`

check if the number is present in the nums array

if number not present in nums :

return number

Time: O(n²)

Space:O(1)

Approach 2:

*Using hash-map*

Using hash map with the above technique considerably reduces the cost of traversing the array each time

`class Solution(object):`

def firstMissingPositive(self, nums):

val=set(nums)

for i in range(1,len(nums)+2):

if i not in val and i>0:

return i

Time: O(n)

Space:O(n)

Approach 3 :

Now to a much more optimized solution.

Here we assume that the number is to be positioned to an index , number - 1 . Iterate through the array and for each of the number currently being explored , swap it with the number at its actual index position. While traversing, if a number is at its correct index position just leave that number and move to the next index position.

`class Solution(object):`

def firstMissingPositive(self, nums):

i=0

while(i<len(nums)):

if nums[i]<=0 or nums[i]>len(nums):

i+=1

else:

if nums[i]==i+1:

i+=1

else:

if nums[nums[i]-1]==nums[i]:

i+=1

else:

temp=nums[nums[i]-1]

nums[nums[i]-1]=nums[i]

nums[i]=temp

j=0

while(j<len(nums)):

if(j+1!=nums[j]):

return(j+1)

j+=1

return(len(nums)+1)

Time: O(n)

Space: O(1)