First Missing Positive - LeetCode Hard

41. First Missing Positive

Hard42.5% acceptance1,698,854 / 4,001,294 submissions

Given an unsorted integer array nums. Return the smallest positive integer that is not present in nums.

You must implement an algorithm that runs in O(n) time and uses O(1) auxiliary space.

Example 1:

Input: nums = [1,2,0]
Output: 3
Explanation: The numbers in the range [1,2] are all in the array.

Example 2:

Input: nums = [3,4,-1,1]
Output: 2
Explanation: 1 is in the array but 2 is missing.

Example 3:

Input: nums = [7,8,9,11,12]
Output: 1
Explanation: The smallest positive integer 1 is missing.

Constraints:

Hints

Hint 1

Think about how you would solve the problem in non-constant space. Can you apply that logic to the existing space?

Hint 2

We don't care about duplicates or non-positive integers

Hint 3

Remember that O(2n) = O(n)