41. First Missing Positive

find_missing_positive.py

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        
        def hashset(numbers):
            set_nums = set(numbers)
            n = len(numbers)
            
            for i in range(1, n + 2): # case A: [1,n] case B: n+1 if A is full i.e. 1 to n
                if i not in set_nums:
                    return i
        
        def optimal(numbers):
            if not numbers:
                return 1
            
            n = len(numbers)
            for i in range(0, n):                               # duplicate
                while 1 <= numbers[i] <= n and numbers[i] != numbers[numbers[i] - 1]:
                    curr_pos = numbers[i]
                    next_pos_idx = curr_pos - 1
                    next_pos = numbers[next_pos_idx]
                    
                    numbers[next_pos_idx] = curr_pos
                    numbers[i] = next_pos
                    
                    # above lines are eq. to:
                    # numbers[numbers[i]-1], numbers[i] = numbers[i], numbers[numbers[i]-1]
            
            missing = -1
            for i in range(n):
                if numbers[i] != i + 1:
                    missing = i + 1
                    break
            if missing == -1:
                missing = len(numbers) + 1
                
            return missing

        
        return optimal(nums)