First Missing Positive — LeetCode 41 Python Solution

The problem

Given an unsorted integer array nums. Return the smallest positive integer that is not present in nums.

Example

Input

nums = [1,2,0]

Output

3

Explanation

The numbers in the range [1,2] are all in the array.

Python solution

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        for i in range(n):
            while 1 <= nums[i] <= n and nums[i] != nums[nums[i] - 1]:
                j = nums[i] - 1
                nums[i], nums[j] = nums[j], nums[i]
        for i in range(n):
            if nums[i] != i + 1:
                return i + 1
        return n + 1

Complexity

Pattern: Hash Map

Trade memory for time: remember what you have seen so the second pass never happens. LeetCode 41. First Missing Positive is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Hash Table.

The hash map guide has the Python template for the pattern and the 709 LeetCode problems that use it.

Related problems