41. First Missing Positive

Solution 1: Sort

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        nums.sort()
        theSmallestSlot = 1
        for i in range(len(nums)):
            # Ignore the non-positive number or duplicate
            if nums[i] <= 0 or (i > 0 and nums[i] == nums[i - 1]):
                continue
            
            if theSmallestSlot == nums[i]:
                theSmallestSlot += 1
            else: # theSmallestSlot != nums[i]
                return theSmallestSlot
            
        return theSmallestSlot

Time Complexity: O(NLog(N))
Space Complexity: O(1)

Solution 2: Set

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        numSet = set(nums)
        for v in range(1, len(nums) + 1):
            if v not in numSet:
                return v
            
        return len(nums) + 1

Time Complexity: O(N)
Space Complexity: O(N)

Solution 3: Swap to the right slot

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        #                                                   0, 1, 2, 3, 4, 5
        # Set the positive number to the right place (e.g, [1, 2, 3, 4, 8, 9])
        for idxOfElmtInRightRange in range(n):
            while 1 <= nums[idxOfElmtInRightRange] <= n:
                rightSlotIdx = nums[idxOfElmtInRightRange] - 1
                if nums[rightSlotIdx] != nums[idxOfElmtInRightRange]:
                    swapTmp = nums[rightSlotIdx]
                    nums[rightSlotIdx] = nums[idxOfElmtInRightRange]
                    nums[idxOfElmtInRightRange] = swapTmp
                else: # The number is in the right slot:
                    break
        
        for i in range(n):
            if nums[i] != i + 1:
                return i + 1
        return n + 1

Time Complexity: O(N)
Space Complexity: O(1)

Reference

https://leetcode.com/problems/first-missing-positive/discuss/17071/My-short-c%2B%2B-solution-O(1)-space-and-O(n)-time