First missing positive integer in an unsorted list

Given an unsorted list of integers that may include negatives, zeros, duplicates and values far larger than the list's length, return the smallest positive integer that does not appear in it. A linear-time solution with extra memory is a fine start; the target is linear time and constant extra space.

Interface

Unless you agree on a different interface with the interviewer, assume:

• first_missing_positive(nums: list[int]) -> int — the smallest integer >= 1 not in nums. You may rearrange or overwrite nums.

Example

first_missing_positive([7, 1, 0, 2, -5])  ->  3
first_missing_positive([2, 3, 4])         ->  1    # 1 is missing, however large the rest are
first_missing_positive([1, 1, 2, 2, 3])   ->  4

Constraints

• 1 <= len(nums) <= 10^5; values are 32-bit signed integers.
• Target: O(n) time, O(1) extra space.

Clarifying questions

• May I modify the input list?
• Does "constant extra space" allow overwriting the input?
• Can values be at the 32-bit limits, so negating or adding might overflow?
• Is a sort, O(n log n), acceptable as a first step?

What a strong answer covers

• The bound: for a list of length n the answer is in 1..n+1, so values outside [1, n] never matter.
• A hash-set solution first, O(n) time and space.
• Cyclic placement: swap each value v in [1, n] into index v - 1 until it is home or a duplicate is already there, then scan for the first index i with nums[i] != i + 1. Each swap places one value for good, so the total is O(n).
• The duplicate check that prevents an endless swap loop, and an alternative that marks presence by negating nums[v - 1] after clearing non-positives.
• Tests: all negatives, [1..n] complete, duplicates, a single element.

Follow-ups

• The input is read-only. What is the best you can do in time and space?
• Return the k smallest missing positive integers.
• The numbers arrive as a stream too large to store. How would you find the answer, or an approximation?