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

Example 1:


Input: [1,2,0]
Output: 3


Example 2:


Input: [3,4,-1,1]
Output: 2


Example 3:


Input: [7,8,9,11,12]
Output: 1


Note:

Your algorithm should run in O(n) time and uses constant extra space.

Difficulty: interview

Starter code:

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        

Solutions:
class Solution:
     def firstMissingPositive(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         nums = sorted(set(nums), key=lambda x: x)
         result = 0
         for i in range(len(nums)):
             if nums[i] <= 0:
                 continue
             elif nums[i] == result + 1:
                 result += 1
             else:
                 break
         return result + 1

class Solution:
     def firstMissingPositive(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         if not nums:
             return 1
         for index in range(len(nums)):
             while nums[index] != index + 1:
                 tmp = nums[index]
                 if tmp <= 0 or tmp > len(nums) or tmp == nums[tmp - 1]:
                     break
                 nums[index] = nums[tmp - 1]
                 nums[tmp - 1] = tmp
         for index in range(len(nums)):
             if nums[index] != index + 1:
                 return index + 1
         return len(nums) + 1


class Solution:
     def firstMissingPositive(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         minSet = set()
         maxSet = set()
         nums = set(nums)
         for num in nums:
 
             if num > 0:
                 if num + 1 in minSet:
                     minSet.remove(num + 1)
                     minSet.add(num)
                     if num - 1 in maxSet:
                         maxSet.remove(num - 1)
                         minSet.remove(num)
                 elif num - 1 in maxSet:
                     maxSet.remove(num - 1)
                     maxSet.add(num)
                     if num + 1 in minSet:
                         maxSet.remove(num)
                         minSet.remove(num + 1)
                 else:
                     minSet.add(num)
                     maxSet.add(num)
                 # print("min set:", minSet)
                 # print("max set:", maxSet)
         if len(minSet) == 0 or len(maxSet) == 0:
             return 1
         return min(maxSet) + 1 if min(minSet) == 1 else 1

class Solution:
     def firstMissingPositive(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         i = 0
         n = len(nums)
         
         if not nums:
             return(1)
         while (i <n):
             while ((nums[i] != i) and (nums[i] > 0) and (i<n) and (nums[i] < n) and (nums[i] != nums[nums[i]])):
                 temp = nums[nums[i]]
                 nums[nums[i]] = nums[i]
                 nums[i] = temp
             i = i + 1
 
         i = 1
         while(i<n):
             if(nums[i] != i):
                 return(i)
             i=i+1
         if(nums[0] == n):
             return(n+1)
         else:
             return(n)
 


class Solution:
     def firstMissingPositive(self, nums):
         for i in range(len(nums)):
             while 0 <= nums[i]-1 < len(nums) and nums[nums[i]-1] != nums[i]:
                 tmp = nums[i]-1
                 nums[i], nums[tmp] = nums[tmp], nums[i]
         for i in range(len(nums)):
             if nums[i] != i+1:
                 return i+1
         return len(nums)+1

class Solution:
     def firstMissingPositive(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         
         if nums == []:
             return(1)
         for _ in range(5):
             for i in range(len(nums)):
                 if ((i + 1) != nums[i]) and (0 < nums[i] <= len(nums)):
                     nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]
                     #print(nums, 'up')
                 else:
                     pass
             #print(nums)
             for i in range(len(nums))[::-1]:
                 if ((i + 1) != nums[i]) and (0 < nums[i] <= len(nums)):
                     nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]
 
                 else:
                     pass
             #print(nums)
         for i in range(len(nums)):
             if not i+1 == nums[i]:
                 #print(nums)
                 return(i+1)
         if sorted(nums) == nums:
             return(len(nums)+1)


class Solution:
     
     def firstMissingPositive(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         A=nums
         n = len(A)
         for index in range(n):
             element = A[index]
             while True:
                 if element <= 0 or element > n or element == A[element - 1]:
                     break
                 A[element - 1], element = element, A[element - 1]
         for index in range(n):
             if A[index] != index + 1:
                 return index + 1
         return n + 1
             


class Solution:
     def firstMissingPositive(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         i = 0
 
         while i < len(nums):
             tmp = nums[i]
             # exchange to its right idx
             while tmp != i + 1 and tmp > 0 and tmp < len(nums):
                 nums[i] = nums[tmp-1]
                 nums[tmp-1] = tmp
                 if tmp == nums[i]:
                     break
                 tmp = nums[i]
             i += 1
         print(nums)
 
         for i in range(len(nums)):
             if nums[i] != i+1:
                 return i+1
         return len(nums) + 1


class Solution:
     def firstMissingPositive(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
 
         # put numbers to their places
         # [-1,0,2,1] -> [1,2,0,0]
         for i in range(len(nums)):
             if nums[i] < 0:
                 nums[i] = 0
                 
             if nums[i] > 0 and nums[i] != i + 1:
                 j, nums[i] = nums[i], 0
                 while 0 < j <= len(nums) and nums[j-1] != j:
                     next_j = nums[j-1]
                     nums[j-1] = j
                     j = next_j
             
         for i, num in enumerate(nums):
             if not num:
                 return i+1
         
         if nums and nums[-1] > 0:
             return nums[-1] + 1
         
         return 1


class Solution:
     def firstMissingPositive(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         minSet = set()
         maxSet = set()
         nums = set(nums)
         for num in nums:
 
             if num > 0:
                 if num + 1 in minSet:
                     minSet.remove(num + 1)
                     minSet.add(num)
                     if num - 1 in maxSet:
                         maxSet.remove(num - 1)
                         minSet.remove(num)
                 elif num - 1 in maxSet:
                     maxSet.remove(num - 1)
                     maxSet.add(num)
                     if num + 1 in minSet:
                         maxSet.remove(num)
                         minSet.remove(num + 1)
                 else:
                     minSet.add(num)
                     maxSet.add(num)
                 print("min set:", minSet)
                 print("max set:", maxSet)
         if len(minSet) == 0 or len(maxSet) == 0:
             return 1
         return min(maxSet) + 1 if min(minSet) == 1 else 1

class Solution:
     def firstMissingPositive(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         nums.append(0)
         for i in range(len(nums)):
             while 0 < nums[i] < len(nums) and nums[i] != i and nums[i] != nums[nums[i]]:
                 temp = nums[nums[i]]
                 nums[nums[i]] = nums[i]
                 nums[i] = temp
                 print((temp, nums))
         for i in range(1, len(nums)):
             if nums[i] != i:
                 return i
         return len(nums)


class Solution:
     def firstMissingPositive(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         if not nums: return 1
         n = len(nums)
         for i in range(len(nums)):
             while nums[i] > 0 and nums[i] <= n and nums[i] != nums[nums[i] - 1]:
                 tmp = nums[i]
                 nums[i] = nums[tmp - 1]
                 nums[tmp - 1] = tmp
         for j in range(len(nums)):
             if nums[j] != j + 1: return j + 1
         return n + 1


class Solution:
     def firstMissingPositive(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         lnums=len(nums)
         for i in range(lnums):
             while 0<nums[i]<=lnums and nums[i]!=nums[nums[i]-1]:
                 tmp=nums[i]
                 print((i,tmp,nums))
                 nums[tmp-1],nums[i]=nums[i],nums[tmp-1]
                 print((i,tmp,nums))
         for i in range(lnums):
             if nums[i]!=i+1:
                 return i+1
         return lnums+1
         
         


class Solution:
     def firstMissingPositive(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         
         if nums == []:
             return(1)
         for _ in range(10):
             for i in range(len(nums)):
                 if ((i + 1) != nums[i]) and (0 < nums[i] <= len(nums)):
                     nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]
                     #print(nums, 'up')
                 else:
                     pass
             #print(nums)
             for i in range(len(nums))[::-1]:
                 if ((i + 1) != nums[i]) and (0 < nums[i] <= len(nums)):
                     nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]
 
                 else:
                     pass
             #print(nums)
         for i in range(len(nums)):
             if not i+1 == nums[i]:
                 #print(nums)
                 return(i+1)
         if sorted(nums) == nums:
             return(len(nums)+1)


class Solution:
     def firstMissingPositive(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         if len(nums) == 0:
             return 1
         nums.append(0)
   
         for i in reversed(range(len(nums))):
             n = nums[i]
             while n>=0 and n<len(nums) and i != n:
                 nums[n], nums[i] = nums[i], nums[n]
                 if n == nums[i]:
                     break
                 n = nums[i]
         print(nums)
         
 
         for i,n in enumerate(nums):
             if i==0:
                 continue
             if i != n:
                 return i
         return nums[-1]+1

class Solution:
     def firstMissingPositive(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         n = len(nums)
         for i in range(n):
             while nums[i] > 0 and nums[i] <= n and nums[i] != i+1 and nums[i] != nums[nums[i]-1]:
                 nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i]-1]
         for i in range(n):
             if nums[i] != i + 1:
                 return i + 1
         return n + 1