You are given an unsorted integer array A which may contain negative numbers and duplicates. Find the smallest missing positive integer. You must solve it in O(N) time and constant extra space.
This represents real-world ID allocation where smallest available ID must be assigned.
Constraints
1 ≤ N ≤ 100000
-10^5 ≤ A[i] ≤ 10^5
Public Test Cases
Input:
3 4 -1 1
Output:
2
Examples
Example 1
Input: [-1, -2, -3]
Output: 1
Example 2
Input: [3, 4, -1, 1]
Output: 2
Example 3
Input: [1, 2, 0]
Output: 3
Loading...
[-1, -2, -3]
1
First Missing Positive in Unsorted Data - Practice - Prepverse 🎓