First Missing Positive

• Problem Statement
  • Example 1:
  • Example 2:
  • Example 3:
• Approach 1

Problem Statement

Given an unsorted integer array, find the smallest missing positive integer. [URL]

Example 1:

Input: [1,2,0]
Output: 3

Example 2:

Input: [3,4,-1,1]
Output: 2

Example 3:

Input: [7,8,9,11,12]
Output: 1

Note: Your algorithm should run in O(n) time and uses constant extra space.

Approach 1

#collapse-hide
from typing import List

class Solution:
    def firstMissingPositive(self, nums: List[int]):
        result = 1
        nums.sort()
        for i in range(len(nums)):
            if nums[i] == result:
                result += 1
        return result

sol = Solution()

sol.firstMissingPositive([7,8,9,11,12])

1

Worst case performance in Time: $O(nlogn)$

Worst case performance in Space: $O(1)$