First Missing Positive
Easy
Given an unsorted integer array nums, find the smallest positive integer that does not appear in the array.
You must solve the problem in O(n) time and use O(1) extra space.
Example 1
Input
n = 3 nums = [1, 2, 0]
Output
3
Explanation
The positive integers start from 1.
1 and 2 are present, but 3 is missing.
Therefore, the answer is 3.
Example 2
Input
n = 4 nums = [3, 4, -1, 1]
Output
2
Explanation
1 is present, but 2 is missing.
Therefore, the smallest missing positive integer is 2.
Constraints
1 <= n <= 10^5
-10^9 <= nums[i] <= 10^9
The solution must run in O(n) time.
Use O(1) extra space.
Hints:
Hint 1
The answer must be between 1 and n + 1.
Hint 2
Try placing every positive number x in the position x - 1.
Auto
Loading editor...
Input
Expected Output