Given an unsorted array, find the smallest positive integer that is missing. It must run in O of n time with constant extra space, so no sorting and no hash set.
DSA Animator › DSA Revision › Arrays › First Missing Positive
Remember: the answer is in 1 to n plus 1, so the array can be its own hash. Place each x at index x minus 1, then find the first misfit. The video solves First Missing Positive (LeetCode 41, Hard) with the Cyclic Placement pattern from the Arrays topic, and you can replay every step in the interactive First Missing Positive animation.
Given an unsorted array, find the smallest positive integer that is missing. It must run in O of n time with constant extra space, so no sorting and no hash set.
For 3, 4, minus 1, 1, the numbers 1, 3 and 4 are present. The smallest missing positive is 2.
Sorting is O of n log n, and a hash set uses O of n space. Both break the rules.
The answer is always between 1 and n plus 1. So use the array itself as the hash: every number x belongs at index x minus 1. Swap numbers into their home, ignoring anything out of range. Then the first index that does not hold its own number gives the answer.
3 belongs at index 2, so swap it there, and minus 1 lands at index 0. Minus 1 is out of range, so we skip it. 4 goes to index 3, which brings 1 back to index 1. 1 belongs at index 0, so swap again, and minus 1 comes back and is skipped. 3 and 4 are already home. Now scan: index 0 holds 1, but index 1 should hold 2, and it does not. So the answer is 2.
In code, for each index, keep swapping while the value is in range and not already at its home. Then scan for the first index i whose value is not i plus 1, and return i plus 1. If every slot is correct, return n plus 1, so it's O of n time and O of 1 space.
Remember: the answer is in 1 to n plus 1, so the array can be its own hash. Place each x at index x minus 1, then find the first misfit.