DSA problem
First Missing Positive
Given an unsorted integer array nums, return the smallest missing positive integer.
You must implement an algorithm that runs in O(n) time and uses O(1) auxiliary space.
The crucial observation is that for an array of length n, the answer must lie in the range [1, n + 1]. Any value outside [1, n] (zeros, negatives, or numbers larger than n) is irrelevant and can be ignored.
We use the array itself as a hash table via cyclic sort: we repeatedly place each value v (where 1 <= v <= n) at index v - 1. After this rearrangement, the first index i whose value is not i + 1 reveals that i + 1 is the smallest missing positive. If every position is correct, the answer is n + 1.
Examples
nums = [1,2,0]3nums = [3,4,-1,1]2nums = [7,8,9,11,12]1Constraints
- 1 <= nums.length <= 10^5
- -2^31 <= nums[i] <= 2^31 - 1
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.