Arrays and Hashing Hash map lookups
66. First Missing Positive
You are given an array of integers nums. Return the smallest positive integer that does not appear in it.
The positive integers are 1, 2, 3 and so on, so 0 and negative numbers are never the answer. The array can hold zeros, negative numbers, very large numbers and repeats.
Aim for O(n) time and O(1) extra memory. You may change nums.
Example 1
Input: nums = [7, 3, -2, 1, 2, 9, 3]
4Explanation: 1, 2 and 3 all appear, and 4 does not. The 7 and the 9 do not matter, because a smaller value is already missing.
Example 2
Input: nums = [4, 2, 1, 3]
5Explanation: Every value from 1 to 4 appears, so the smallest missing one is 5.
Example 3
Input: nums = [-2147483648, 0, 2147483647]
1Explanation: 0 and the negative number are not positive, and the only positive value is far above 1. So 1 is missing.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ nums.length ≤ 105-231 ≤ nums[i] ≤ 231 − 1
Clarifying questions
What you would ask an interviewer before writing any code.