First Missing Positive
Picture
With n items, the first missing positive lies between 1 and n+1. Values outside 1..n cannot fill those n positions.
Predict
Why stop swapping when the destination already holds the same value?
Walk through the small example
To avoid a duplicate loop. The answer range maps useful values directly to array positions.
Mental model and complete Python solution
The array becomes a temporary membership table. Each useful x tries to occupy slot x−1. A value is moved only until it is home or blocked by its duplicate.
What the function promises: Return the smallest missing positive and mutate the integer list.
def first_missing_positive(values):
n = len(values)
i = 0
while i < n:
value = values[i]
home = value - 1
if 1 <= value <= n and values[home] != value:
values[i], values[home] = values[home], values[i]
else:
i += 1
for i, value in enumerate(values):
if value != i + 1:
return i + 1
return n + 1
assert first_missing_positive([3,4,-1,1]) == 2
assert first_missing_positive([1,2,0]) == 3Work and storage: O(n) time and O(1) auxiliary space; every successful swap homes at least one value.
When to recognize it: The answer range maps useful values directly to array positions.
Check before applying it: Duplicates require a loop guard, and the method mutates input.
Change one rule
Input mutation is forbidden.
See what changes
Use an O(n) membership set, or a bitset when its storage is allowed.
Connect
Dutch flag: grow three regions: Both grow meaningfully classified positions in place.
sets: A set is simpler when O(n) extra storage is acceptable.