First Missing Positive
Find the smallest positive integer absent from nums in linear time and constant extra space.
Intuition
A hash set makes the answer easy, but it uses O(n) extra memory; sorting avoids that memory but costs O(n log n). For an array of length n, the first missing positive must lie in 1..n + 1, so values outside 1..n cannot affect which position fails first. Use the array itself as a hash table by placing value v at index v - 1. After every placeable value reaches its home, the first index not containing index + 1 reveals the answer.
A linear-time, constant-space missing-number problem over a bounded value range suggests using indices as hash slots. When value v naturally belongs at v - 1, in-place cyclic placement can replace an external set.
Approach
Restrict attention to values that can occupy the array
Only integers from 1 through n have a home index inside the array. Negatives, zero, and values above n may remain anywhere because if all values 1..n exist, the answer is n + 1; otherwise one of those in-range values is missing.
Swap each positive into its value-indexed home
At index i, while nums[i] is in 1..n and its home does not already contain the same value, swap it with nums[nums[i] - 1]. Use a while, not an if, because the incoming value may also belong elsewhere. The duplicate check prevents an infinite swap between equal values.
Find the first broken value-to-index match
Scan from index zero. If nums[i] != i + 1, then every smaller positive has already appeared in its earlier home and i + 1 is the first missing one. If every home is correct, return n + 1. Each successful swap permanently places at least one value, so total work is O(n).
Solution
Common pitfalls
Treating zero as a placeable value
while 0 <= nums[i] < n:
while 1 <= nums[i] <= n:
The tracked values are positive 1 through n; zero has no valid value - 1 home.
Using one swap instead of a placement loop
if 1 <= nums[i] <= n:
while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
A swap brings a new value to index i, and that value may also need to move before the index is settled.
Returning the zero-based mismatch
return i
return i + 1
Index zero represents positive value 1, so the missing value is always one greater than its home index.
Edge cases
[-3, -1]No swaps occur, index zero does not contain 1, and the method returns 1.
[1, 1]The home-equality condition stops duplicate 1s from swapping forever; the scan then returns 2.
All value-index matches succeed, so the answer is the next positive n + 1.