Back to DSA sheet
First Missing Positive
HardArraysGiven an unsorted array, find the smallest positive integer that does not appear. Run in O(n) time and use O(1) extra space.
Input format (stdin): the first line has n. The second line has n integers (may be empty when n is 0). Output the smallest missing positive.
Examples
Input: 3
1 2 0
Output: 3
1 and 2 are present, so 3 is missing.
Input: 4
3 4 -1 1
Output: 2
2 is the smallest missing positive.
Input: 3
7 8 9
Output: 1
No 1, so the answer is 1.
Constraints
- 0 <= n <= 10^5
- -2^31 <= nums[i] <= 2^31 - 1
Sheets
NeetCode 250
first-missing-positive.cpp3 sample tests
Loading editor
Test results
Run the sample tests to check your solution against expected output.
Custom input (stdin)
Output
Run your code to see its output.