41. First Missing Positive - cocoder39/coco39_LC GitHub Wiki

41. First Missing Positive

solution 1:

  • if value A at index i is within [1, n] is present, flag the index at A-1 to negative value
  • pitfall: index i could have been flagged, so A could be negative. using abs(A)
  • for value < 1 or > n, they are of no use. set them to n+2, which then doesn't affect the first missing value as first missing value could be within [1, n+1]. (it could be n+1 if 1 to n are all present)
class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)

        for i, num in enumerate(nums):
            if num <= 0 or num > n:
                nums[i] = n+2
        
        for i, num in enumerate(nums):
            if 1 <= abs(num) <= n and nums[abs(num)-1] > 0:
                # index i could have been flagged
                # attempt to flag the index abs(num)-1
                nums[abs(num)-1] *= -1

        for i, num in enumerate(nums):
            if num > 0:
                return i + 1
        
        return n + 1

Solution 2: cycle sort

  • the desired state is that for each value = nums[i] it is paced at index value - 1 (eg, 1 is at index 0, 2 is at index 1, etc)
  • for each value in between 1 and n, move it to its desired index.
  • check each index to find the first index that doesn't hold the desired value
class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)

        i = 0
        while i < n:
            correct_idx = nums[i] - 1
            if 1 <= nums[i] <= n and nums[i] != nums[correct_idx]:
                # nums[correct_idx] is in desired state after swamping.
                # nums[i] may not be in desired state so continue to process i

                # if condition ensures this line changes nums[correct_idx] to desired state
                # nums[correct_idx] only has single desired state
                # state of nums[correct_idx] will be changed at most once
                # it won't lead to endless loop
                nums[i], nums[correct_idx] = nums[correct_idx], nums[i]
            else:
                i += 1
        
        for i in range(n):
            if nums[i] != i + 1:
                return i + 1
        
        # 1 to n are all present
        return n + 1
⚠️ **GitHub.com Fallback** ⚠️