41. First Missing Positive

Problem¶

Given an unsorted integer array, return its smallest missing positive integer in \(O(n)\) time and \(O(1)\) auxiliary space. The array may be modified.

nums = [3, 4, -1, 1] -> 2

Key trick¶

For an array of length \(n\), the answer is in \([1, n + 1]\). Place every value x in \([1,n]\) at index x - 1; the first index not containing its expected value identifies the answer.

Trap¶

Ignoring duplicates can cause an infinite swapping loop.
Negative numbers, zero, and values greater than \(n\) must be ignored.
Sorting or using a set violates the required time or auxiliary-space bound.
Each swap must recheck the new value placed at the current index.

Why is it interesting?¶

It uses the input array as an implicit presence table, achieving both linear time and constant auxiliary space through cyclic placement.

Python solution¶

class Solution:
    def firstMissingPositive(self, nums: list[int]) -> int:
        n = len(nums)

        for i in range(n):
            # Put each relevant value x at its natural index x - 1.
            while (
                1 <= nums[i] <= n
                and nums[nums[i] - 1] != nums[i]
            ):
                idx = nums[i] - 1
                nums[i], nums[idx] = nums[idx], nums[i]

        # The first incorrect position represents the missing value.
        for i, x in enumerate(nums):
            if x != i + 1:
                return i + 1

        return n + 1

Time: \(O(n)\) because every swap places at least one value in its final position.
Auxiliary space: \(O(1)\).

Comment on my solution¶

Your rejection of a single-pass greedy approach is correct: encountering values out of order prevents safely advancing the answer.

The submitted algorithm repeatedly partitions and rescans a suffix whenever smallest reaches min_largest. Those rescans can process the same elements many times, producing \(O(n^2)\) worst-case time and causing the timeout.

The min_largest and moving boundary also make the invariant difficult to verify. Directly mapping each relevant value x to index x - 1 gives every value one canonical position and guarantees linear total work.

# Ideas:
# - greedy doesn't work:
#   - because if we have smallest (starting at 1), and increment
#     it each time encounter it while scanning, and 2 comes before
#     1 in nums ([2, 1]), then we'll set smallest to 2 which is wrong.
# - What about a min heap of 2 elements
# - split in two 2 intervals keeping only end of first and beg of sencond
#   - [1, ..., 4] - [7, ...] -> 5
#   - yeah it seems to be a partinioning problem
#     - what about something like the national deutch flag algo

# WRONG:
# Time Limit Exceeded: 178/179 testcases passed
class Solution:
    def firstMissingPositive(self, nums: list[int]) -> int:
        # [1,2,0]       -> 3
        # [2,1]         -> 3
        # [3,4,-1,1]    -> 2
        # [7,8,9,11,12] -> 1
        n = len(nums)
        smallest = 1
        min_largest = float("inf")
        i, r = 0, n - 1
        while i < n:
            if r < i:
                if smallest < min_largest:
                    break
                else:
                    min_largest = float("inf")
                    r = n - 1

            if nums[i] <= 0:
                i += 1
            elif nums[i] > smallest:
                min_largest = min(min_largest, nums[i])
                nums[i], nums[r] = nums[r], nums[i]
                r -= 1
                # don't advance i because not processed yet
            elif nums[i] == smallest:
                smallest += 1
                i += 1
            else:
                i += 1
        return smallest