[LeetCode] 41. First Missing Positive

Problem : https://leetcode.com/problems/first-missing-positive/

Positive numbers start from 1. 

Solution 1: 

Use hash set to record all the exiting numbers. Then iterate from 1 and return the first number not in hash set.

Time complexity = O ( N )

Space complexity = O ( N )

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        memo = set(nums)
        
        i = 1
        while i in memo:
            i += 1
        
        return i

Solution 2:

In perfect case, the array contains the contiguous numbers starts from 1.

Such as:  [1, 2, 3, 4, 5, ...]

As it shows,  nums[i]  - 1 == i

Use the array-index to record existing numbers.

For all existing number,  nums[ nums[i] - 1 ]  == nums[i].

The missing number is the first item which nums[i] != i + 1

Time complexity = O ( 2 * N )

Space complexity = O ( N )

class Solution(object):
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        
        for i in range(len(nums)):
            while nums[i] > 0 and nums[i] <= len(nums) and nums[nums[i]-1] != nums[i]:
                # swap nums[i] and nums[nums[i] -1]
                # must save nums[i] with tmp
                # because current value of nums[i] 
                # will be used to calculate index
                tmp = nums[i]  
                nums[i] = nums[nums[i]-1]
                nums[tmp-1] = tmp
                
        
        for i in range(len(nums)):
            if nums[i] != i + 1:
                return i + 1
        
        return len(nums) + 1