First Missing Positive

Cyclic Sort

30 min

Problem Statement

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.

Example

Example 1:

Input: nums = [1,2,0]

nums: [1, 2, 0]

Output: 3

Solution

The problem can be solved in O(n) time and O(1) extra space using cyclic sort. The idea is to place each number in its correct position. For example, 1 should be at index 0, 2 at index 1, and so on. After sorting, we can iterate through the array to find the first number that is not in its correct place.

Algorithm Steps

Iterate through the array. For each number, if it's within the range [1, n] and not in its correct place, swap it with the number at its correct index.
Repeat this process until all numbers are in their correct places or are out of range.
Iterate through the sorted array. The first index `i` where `nums[i] != i + 1` gives us the first missing positive, which is `i + 1`.
If all numbers are in their correct places, the first missing positive is `n + 1`.

First Missing Positive

Cyclic Sort Approach

Input: nums = [1, 2, 0]

Output: ?

Progress1 / 1

Ready to start the visualization

Nums

First Missing Positive Solution


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