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, 5, 1]
Output: 4
Explanation: 1, 2, 3, 5 are present; 4 is the smallest missing positive.
Example 2
Input: [-2, -1, 0, 1]
Output: 2
Explanation: Only 1 is present among positive integers; 2 is missing.
Example 3
Input: [4, 2, 6, 3]
Output: 1
Explanation: 1 is missing; 2, 3, 4, 6 are present.
Constraints
Case 1
Input: [5, 7, 8, 2, 3]
Expected: 1
Case 2
Input: [1, 1, 1, 1]
Expected: 2
Case 3
Input: [1, 2, 3, 4, 5, 6]
Expected: 7
Case 4
Input: [0, -1, -2, -3]
Expected: 1
Case 5
Input: [10, 11, 12, 13]
Expected: 1