LC41 First Missing Positive

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        """ O(N)/O(1)
        in order to find first missing positive, need to make sure array sorted 
        1. loop through num, take num-1 as idx, place num to sorted order (not num is within [0,N])
        2. loop array, if nums[i]-1 != i, i+1 the first missing positive number(here solves case when all numbers >N, since in that case return 1 and i+1 = 1 ) 
        3. if after loop, all numbers are at the right place, return N +1 
        
        """ 
        size = len(nums)
        for i in range(size):
        # why using <= size ? for test case [5,11,7,9], each number is bigger than index 0 +1, so  first missing positive is 1;
            while 0 < nums[i] <= size and nums[nums[i]-1] != nums[i]:
                #nums[i], nums[nums[i] - 1] = nums[nums[i] - 1], nums[i]   # here can't swap directly or else will cause TLE
                self.swap(nums,nums[i]-1,i)
        for i in range(size):
            if nums[i]-1 != i:
                return i+1
        return size + 1 # for test case [1,2,3] if each element is at right position, then missing one should be size +1 
        
    def swap(self,arr,idx1,idx2):
        arr[idx1],arr[idx2] = arr[idx2],arr[idx1]