First Missing Positive

Problem

An ID allocator hands out integer handles but drops and corrupts entries freely. Given the unsorted pool of handles it currently holds - arbitrary integers, negatives included - find the smallest positive integer that is missing. The catch: you must do it in O(n) time and O(1) extra space, which rules out sorting and rules out a separate hash set.

Example 1:

Input: nums = [4, -3, 1, 9]
Output: 2
Explanation: 1 is present but 2 is not, so 2 is the smallest missing positive.

Example 2:

Input: nums = [22, 24, 26]
Output: 1
Explanation: no value in [1, 4] appears at all; the smallest missing positive is 1.

Example 3:

Input: nums = [1, 2, 3]
Output: 4
Explanation: every positive from 1 to n is present, so the answer is n + 1.

Constraints:

• 1 <= nums.length <= 10^5
• -10^5 <= nums[i] <= 10^5

Solution Breakdown

Approach - cyclic-sort placement using the array as its own hash table.

The answer lives in [1, n+1]: the n slots can only certify presence of values 1 through n, and if all of those are present the answer is exactly n + 1. That bound is what makes an in-place solution possible - you only ever need to track n possible values, and the array already has n slots. The algorithm sends every value v in [1, n] to index v - 1 so that afterwards nums[i] == i + 1 means "the positive i + 1 is present". The index plays the key, the value sitting in it plays the membership flag - no external set needed.

The placement loop is a while, not an if: after swapping a value into its home, the value that lands at the current index may itself be placeable, so the slot keeps swapping until it holds either an out-of-range number (a negative, zero, something above n - all irrelevant to positives) or a value whose home is already occupied by an identical value (the duplicate guard nums[nums[i] - 1] != nums[i]; without it, [1, 1] would swap with itself forever). Each swap parks one value in its final resting place for good, so the total swap count across the whole outer loop is at most n even though the loop nests. A final left-to-right scan finds the first slot not holding its own index-plus-one; that index plus one is the smallest missing positive. Trace [4, -3, 1, 9]: index 0 swaps 4 into slot 3 ([9, -3, 1, 4]), 9 is out of range; index 2 swaps 1 into slot 0 ([1, -3, 9, 4]); the scan stops at index 1, which holds -3 - answer 2.

Edge cases - all-irrelevant values like [22, 24, 26] trigger zero swaps and return 1 immediately; a complete run [1, 2, 3] falls through the scan and returns n + 1; duplicates like [1, 1] are absorbed by the guard (the second 1 has its home already occupied).

Complexity - O(n) time, O(1) extra space - each value moves into its home at most once (at most n swaps total, outer loop n iterations, scan n), and all state lives in the input array itself.