First Missing Positive

Given an unsorted integer array nums. Return the smallest positive integer that is not present in nums.

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

Example 1:

Input: nums = [1,2,0] Output: 3 Explanation: The numbers in the range [1,2] are all in the array.

Example 2:

Input: nums = [3,4,-1,1] Output: 2 Explanation: 1 is in the array but 2 is missing.

Example 3:

Input: nums = [7,8,9,11,12] Output: 1 Explanation: The smallest positive integer 1 is missing.

Constraints:

• 1 <= nums.length <= 105
• -231 <= nums[i] <= 231 - 1

Approach: Index as a Hash Table (Cyclic Placement)

Algorithm

1. The answer must be in the range [1, n + 1] where n is the array length
2. For each index i, repeatedly place nums[i] at its correct position (nums[i] - 1) as long as it is in [1, n] and not already placed
3. After placement, scan for the first index where nums[i] != i + 1; that value is the answer
4. If all positions are correct, the answer is n + 1

Time & Space Complexity

• Time Complexity: O(n) - each element is swapped into place at most once
• Space Complexity: O(1) - in-place rearrangement, no extra data structures

Java Implementation

public class FirstMissingPositive {

    /**
     * Return the smallest missing positive integer.
     * @param nums Unsorted array
     * @return Smallest missing positive integer
     */
    public static int firstMissingPositive(int[] nums) {
        int n = nums.length;

        for (int i = 0; i < n; i++) {
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                swap(nums, i, nums[i] - 1);
            }
        }

        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }

        return n + 1;
    }

    private static void swap(int[] nums, int a, int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }

    // Test method
    public static void main(String[] args) {
        int[] nums1 = {1, 2, 0};
        System.out.println("Input: nums = [1,2,0]");
        System.out.println("Output: " + firstMissingPositive(nums1)); // Expected: 3

        int[] nums2 = {3, 4, -1, 1};
        System.out.println("Input: nums = [3,4,-1,1]");
        System.out.println("Output: " + firstMissingPositive(nums2)); // Expected: 2

        int[] nums3 = {7, 8, 9, 11, 12};
        System.out.println("Input: nums = [7,8,9,11,12]");
        System.out.println("Output: " + firstMissingPositive(nums3)); // Expected: 1
    }
}

Example Walkthrough

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

1. i=0, num=3: place 3 at index 2. Array -> [1, 4, 3, -1] (after swap 3 and -1), then num=1, place 1 at index 0. Array -> [1, 4, 3, -1]
2. i=1, num=4: place 4 at index 3. Array -> [1, -1, 3, 4]
3. i=2, num=3: already at correct position
4. i=3, num=4: already at correct position
5. Scan: index 1 has -1 != 2, answer is 2

Key Points

1. Answer Bound: The missing positive is always in [1, n + 1]
2. Cyclic Placement: Placing x at index x - 1 turns the array into an implicit hash table
3. Skip Invalid Values: Numbers outside [1, n] are ignored
4. O(n) Time: Each swap puts an element in its final place, so swaps total O(n)
5. O(1) Space: Meets the strict auxiliary space requirement