MANG Problem #27: First Missing Positive (Hard)

1. Problem Statement

Given an unsorted integer array nums, return the smallest missing positive integer.

You must implement an algorithm that runs in $O(n)$ time and uses $O(1)$ auxiliary space.

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

2. Approach: Cyclic Sort (Index as Map)

The smallest missing positive must be in the range [1, n+1].

The Insight

If the array has size n, and the numbers were perfectly sorted from 1 to n, then nums[0] would be 1, nums[1] would be 2... nums[i] would be i + 1.

The Strategy

We will iterate through the array and try to "place" every number x at its correct index x - 1.

If nums[i] = 3, we swap it with the element at nums[2].
We only swap if:
1. nums[i] is positive.
2. nums[i] is within bounds ($\le n$).
3. nums[i] is not already at the correct spot.

3. Java Implementation

public int firstMissingPositive(int[] nums) {
    int n = nums.length;
    
    // 1. Cyclic Sort
    for (int i = 0; i < n; i++) {
        while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
            // Swap nums[i] with nums[nums[i]-1]
            int temp = nums[nums[i] - 1];
            nums[nums[i] - 1] = nums[i];
            nums[i] = temp;
        }
    }
    
    // 2. Find first index mismatch
    for (int i = 0; i < n; i++) {
        if (nums[i] != i + 1) {
            return i + 1;
        }
    }
    
    return n + 1;
}

4. 5-Minute "Video-Style" Walkthrough

The "Aha!" Moment: You don't need a HashSet. The array is your HashSet. By swapping numbers into their "correct" index, you are using the array's memory as a frequency map.
The While Loop: Why a while and not an if? Because after a swap, the new number at nums[i] might also need to be swapped to a different index.
The Range: If the array is [1, 2, 3], the missing one is 4. If it's [1, 1, 1], the missing one is 2. The loop handles both cases.

5. Interview Discussion

Interviewer: "Is the time complexity really O(N) with that nested while loop?"
You: "Yes. Although there is a nested loop, every swap puts at least one number into its final correct position. A number can be swapped at most once to its final position, so the total number of swaps across all iterations is at most $N$."
Interviewer: "What if the input is immutable?"
You: "Then $O(1)$ space is impossible if we must return the answer in $O(N)$ time. We would need to use $O(N)$ extra space for a Set or a copy of the array."