13. First Missing Positive

Hard · Array

Given an unsorted array of integers, find the smallest missing positive integer. A positive integer is an integer greater than 0.

You must solve this problem in O(n) time complexity and O(1) space complexity (ignoring the space used by the input array itself).

Examples

Example 1
Input: [1, 2, 0]
Output: 3
Explanation: The positive integers are 1 and 2. The smallest missing positive is 3.
Example 2
Input: [3, 4, -1, 1]
Output: 2
Explanation: The positive integers present are 1, 3, and 4. The smallest missing positive is 2.

Constraints