# 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)

--

--

Tech-Enthusiast, Coder,Explorer,Geeky,Software Engineer |A piece of code delivers everything that you need. The world is all about codes.