41. First Missing Positive

'''
Given an unsorted integer array nums, return the smallest missing positive integer.
You must implement an algorithm that runs in O(n) time and uses constant extra space.
'''
class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n=len(nums)
        mval=max(nums)
        for i in range(n):
            if nums[i]<=0:
                nums[i]=float('inf')

        for i,j in enumerate(nums):
            j=abs(j)
            if 0<j<=n and nums[j-1]>0:
                nums[j-1]=-1*nums[j-1]


        for i in range(1,n+1):
            if nums[i-1]>0:return i
        else:
            return n+1
'''
Basic idea:
    1. for any array whose length is l, the first missing positive must be in range [1,...,l+1],
        so we only have to care about those elements in this range and remove the rest.
    2. we can use the array index as the hash to restore the frequency of each number within
         the range [1,...,l+1]
'''