First missing positive

Dhanaraj S
2 min readSep 28, 2021

--

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)

--

--

Dhanaraj S

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