First Missing Positive
Hard Cyclic sort
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return the smallest positive integer that is not in an unsorted array, in O(n) time and O(1) extra space.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the smallest positive number that's not in the array, in O(n) time and O(1) space.
Why this works: the answer is between 1 and n+1. Put each value v in 1..n into its "home" index v-1 by swapping; then the first home that has the wrong value tells you the answer.
Example: [3, 4, -1, 1]
place 3 at index 2 → [-1, 4, 3, 1]place 4 at index 3 → [-1, 1, 3, 4]place 1 at index 0 → [1, -1, 3, 4]index 1 should hold 2 → answer 2
✦Hints open one at a time
↗Approach
Cyclic sort: for each index, while its value is in range and not already at its home (and the home doesn't already hold the same value), swap it home. Each swap places one value correctly, so total work is O(n). Then scan for the first mismatch.
</>Solution (Java)
class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; i++) {
while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
int home = nums[i] - 1; // send value to its home index
int t = nums[home];
nums[home] = nums[i];
nums[i] = t;
}
}
for (int i = 0; i < n; i++) {
if (nums[i] != i + 1) return i + 1;
}
return n + 1;
}
}!Common mistake
Swapping when nums[v - 1] already equals v (a duplicate) — that loops forever. Compare with the home slot, not with i + 1.
- Time: O(n).
- Space: O(1).
