First Missing Positive in Unsorted Data

MediumArrayStringHashingIndex MappingOptimizationIn-place Algorithm

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...

Input:

[-1, -2, -3]

Expected Output:

First Missing Positive in Unsorted Data

Constraints

Public Test Cases

Input:

Output:

Examples

Hint 1

Hint 2