First Missing Positive

Given an unsorted integer array (values can be negative, zero, or arbitrarily large), find the smallest missing positive integer — in O(n) time and O(1) extra space.

Example

Input: 3 4 -1 1 Output: 2

Approach

The capstone cyclic-sort problem: the answer must be somewhere in 1..n+1 (with n elements, you can't be missing anything past n+1), so only values in range 1..n are worth placing — cyclic-sort every such value to home index value - 1, ignoring anything negative, zero, or too large to matter. Then scan once: the first index whose value isn't index + 1 gives the answer; if every index matches, the answer is n + 1.

Walkthrough

Cyclic-sorting [3, 4, -1, 1] into place before the final scan:

1def first_missing_positive(nums):
2    n = len(nums)
3    i = 0
4    while i < n:
5        correct = nums[i] - 1
6        if 0 <= correct < n and nums[i] != nums[correct]:
7            nums[i], nums[correct] = nums[correct], nums[i]
8        else:
9            i += 1
10    for i in range(n):
11        if nums[i] != i + 1:
12            return i + 1
13    return n + 1

Input format

Line 1: the array, space-separated

Print the smallest missing positive integer.