Given an unsorted integer array arr, return the smallest positive integer that does not appear in arr. The solution must run in O(n) time and use O(1) extra space.
Example 1
Input: [2, 3, 1, 5, 4]
Output: 6
Explanation: All positive integers from 1 to 5 are present. The smallest missing positive integer is 6.
Example 2
Input: [0, -2, 2, 1]
Output: 3
Explanation: Positive integers 1 and 2 are present. The smallest missing positive integer is 3.
Example 3
Input: [10, 12, 13]
Output: 1
Explanation: No positive integers less than 10 are present. The smallest missing positive integer is 1.
Constraints
Case 1
Input: [5, 4, 3, 2, 1]
Expected: 6
Case 2
Input: [-1, -2, -3, 0]
Expected: 1
Case 3
Input: [1, 1, 1, 1]
Expected: 2
Case 4
Input: [2, 2, 2, 2]
Expected: 1
Case 5
Input: [1, 2, 4, 5, 6]
Expected: 3