first-missing-positive

< Previous 　　　　　　　　　　　　　　　　 Next >

41. First Missing Positive (Hard)

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 constant extra space.

 

Example 1:

Input: nums = [1,2,0]
Output: 3

Example 2:

Input: nums = [3,4,-1,1]
Output: 2

Example 3:

Input: nums = [7,8,9,11,12]
Output: 1

 

Constraints:

• 1 <= nums.length <= 5 * 105
• -231 <= nums[i] <= 231 - 1

Related Topics

[Array] [Hash Table]

Similar Questions

1. Missing Number (Easy)
2. Find the Duplicate Number (Medium)
3. Find All Numbers Disappeared in an Array (Easy)
4. Couples Holding Hands (Hard)

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)