First Missing Positive

cyclic-sortarray

Problem

Given an unsorted integer array nums, return the smallest missing positive integer. Your algorithm must run in O(n) time and use O(1) extra space.

Examples

Example 1

Input: nums = [1,2,0]

Output: 3

Explanation: 1 and 2 are present, 3 is the smallest missing positive.

Example 2

Input: nums = [3,4,-1,1]

Output: 2

Explanation: 1 is present, 2 is missing.

Constraints

•1 <= nums.length <= 10^5
•-2^31 <= nums[i] <= 2^31 - 1

Hints

Hint 1

A hash set of all positive values, then checking 1, 2, 3, ... in order until one is missing, is correct in O(n) time — but again costs O(n) space, disallowed here.

Hint 2

The answer is guaranteed to be in [1, n+1] — so only values in that narrow range are ever relevant, everything else (negatives, zero, values > n) can be ignored.

Hint 3

Cyclic sort: repeatedly swap each in-range value to its 'correct' index (value v belongs at index v-1) — afterward, the first index that doesn't hold its expected value reveals the answer.

Solutions

public int firstMissingPositiveHashSet(int[] nums) {
    Set<Integer> present = new HashSet<>();
    for (int n : nums) present.add(n);
    int i = 1;
    while (present.contains(i)) i++;
    return i;
}

Time: O(n) · Space: O(n) — violates the problem's O(1) space requirement