41. First Missing Positive (hard)

First Try: TLE

I was like.. why does it make TLE???? it seemed like there was only one for loop

HOwever "if i not in nums:" also takes O(n).. which makes the Time Comp O(n^2)

Even so it needs some optimization

In the for loop, we only have to iter till the length of the list, and if theres no return value then return n+1

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        # 1
        # if max(nums)<0:
        #     n = 2
        # else:
        #     n= max(nums)+2
        # for i in range(1, n):
        #     if i not in nums:
        #         return i

        # TLE

        # 2
        # n = len(nums)
        # seen = [False]*(n+1)
        # for num in nums:
        #     if 0<num<=n:
        #         seen[num] = True

        # for i in range(1, n+1):
        #     if not seen[i]:
        #         return i
        # return n+1

        # Time comp: O(n): O(2n) == O(n)
        # Space comp: O(n): seen array

        # 3 Cycle sort
        # sort array in-place, constant time

        n = len(nums)
        i =0
        while i<n:
            curr = nums[i]-1
            if 0<nums[i] <=n and nums[i]!=nums[curr]:
                nums[i], nums[curr] = nums[curr], nums[i]
            else:
                i+=1
        for i in range(n):
            if nums[i] != i+1:
                return i+1
        return n+1
        
        # Time Comp : O(n) .. O(2n): while loop, for(n)
        # Space Comp : O(1) .. input array.. no additional space needed.

Scnd one is using seen arr, inited by false

for each of nums, check its value to seen arr, then on the scnd loop we check if its seen

but it needs more array, so it takes O(n) space comp.

 

Finally I used Cycle sort to make Space comp O(1)

Just sort the array, then check if they're ok

 

From the last part, 

nums[i], nums[curr] = nums[curr], nums[i]

I learned that this can swap values w/o using additional tmp space by tuple unpacking