First Missing Positive

NeetCode: First Missing Positive · LeetCode: 41. First Missing Positive · Difficulty: Hard

Given an unsorted integer array nums, return the smallest positive integer that is not in it. Aim for O(n) time and O(1) extra space.

Example

Text

Input:  nums = [1, 2, 0]         Output: 3
Input:  nums = [3, 4, -1, 1]     Output: 2
Input:  nums = [7, 8, 9, 11, 12] Output: 1

Brute force: put everything in a HashSet

The answer is between 1 and n + 1 (with n numbers, at most n positive values can be present, so some value in 1 to n + 1 is missing). Load all numbers into a HashSet<Integer>, then test 1, 2, 3, ... until one is absent. Sorting and scanning also works, in O(n log n). The set uses O(n) space.

Java

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int firstMissingPositive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int x : nums) {
            set.add(x);
        }
        int x = 1;
        while (set.contains(x)) {
            x++;
        }
        return x;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.firstMissingPositive(new int[]{1, 2, 0}));
        System.out.println(s.firstMissingPositive(new int[]{3, 4, -1, 1}));
        System.out.println(s.firstMissingPositive(new int[]{7, 8, 9, 11, 12}));
        System.out.println(s.firstMissingPositive(new int[]{}));
    }
}

Output

Time: O(n). Space: O(n).

Optimal: cyclic placement with swaps

Since the answer lies in 1 to n + 1, the array itself can serve as the hash set: value v (when 1 <= v <= n) belongs at index v - 1. Walk the array; while nums[i] is in range and not already at its home position, swap it there. Every swap puts one value at its final index for good, so the total number of swaps is at most n. The check nums[nums[i] - 1] != nums[i] also stops on duplicates, which would otherwise loop forever.

After this pass, scan for the first index i with nums[i] != i + 1; the answer is i + 1. If every slot is correct, the answer is n + 1.

For [3, 4, -1, 1]: swap 3 to index 2 giving [-1, 4, 3, 1], swap 4 to index 3 giving [-1, 1, 3, 4], swap 1 to index 0 giving [1, -1, 3, 4]. Index 1 holds -1, so the answer is 2.

Java

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                int home = nums[i] - 1;
                int tmp = nums[home];
                nums[home] = nums[i];
                nums[i] = tmp;
            }
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return n + 1;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.firstMissingPositive(new int[]{1, 2, 0}));
        System.out.println(s.firstMissingPositive(new int[]{3, 4, -1, 1}));
        System.out.println(s.firstMissingPositive(new int[]{7, 8, 9, 11, 12}));
        System.out.println(s.firstMissingPositive(new int[]{}));
        System.out.println(s.firstMissingPositive(new int[]{1, 1}));
    }
}

Output

Time: O(n); each swap fixes one value permanently, so the inner loop runs at most n times in total. Space: O(1) extra; the method reorders the input array in place, so a caller that needs the original order must copy it first. The guard checks the range before using nums[i] as an index, so values such as -1 or n + 1 never index outside the array.