Numbered lockers 1 to n: put each key in its own locker, and any empty locker or doubled key shows what's missing or repeated.
Clues that point here
→ Numbers in the range 1..n or 0..n
→ Find the missing, duplicate or first missing positive
→ O(1) extra space and O(n) time
Not this pattern when
✕ Values aren't bounded by the array length
✕ You may not modify the input
The template
A skeleton to adapt. The parts in comments are what changes from problem to problem.
Index as Hash (Cyclic Sort) · template
int i = 0;
while (i < nums.length) {
int correct = nums[i] - 1; // where this value belongs
if (nums[i] > 0 && nums[i] <= nums.length && nums[i] != nums[correct]) {
int tmp = nums[i]; nums[i] = nums[correct]; nums[correct] = tmp;
} else {
i++;
}
}
for (i = 0; i < nums.length; i++) if (nums[i] != i + 1) return i + 1; // first gap
return nums.length + 1;