First Missing Positive

Given an unsorted array of integers (which may include negatives, zeros, and duplicates), return the smallest positive integer that isn't in the array.

LeetCode: 41. First Missing Positive

Example

Text

Input:  [2, 3, -7, 6, 8, 1, -10, 15]    Output: 4
Input:  [3, 2, -1, 1]                   Output: 4
Input:  [7, 8, 9, 11, 12]               Output: 1

The answer is always between 1 and n + 1: an array of n elements can hold at most the values 1 to n, and if it holds all of them, the answer is n + 1.

Brute force: check 1, 2, 3, ...

Java

public class Main {
    static boolean contains(int[] nums, int k) {
        for (int x : nums) {
            if (x == k) return true;
        }
        return false;
    }

    static int firstMissingPositive(int[] nums) {
        int k = 1;
        while (contains(nums, k)) k++;
        return k;
    }

    public static void main(String[] args) {
        System.out.println(firstMissingPositive(new int[]{2, 3, -7, 6, 8, 1, -10, 15}));
        System.out.println(firstMissingPositive(new int[]{3, 2, -1, 1}) + " " + firstMissingPositive(new int[]{7, 8, 9, 11, 12}));
    }
}

Output

4
4 1

Time: O(n²): up to n + 1 candidates, each a linear search. Space: O(1).

Better: a HashSet

Java

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

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

    public static void main(String[] args) {
        System.out.println(firstMissingPositive(new int[]{2, 3, -7, 6, 8, 1, -10, 15}));
        System.out.println(firstMissingPositive(new int[]{3, 2, -1, 1}) + " " + firstMissingPositive(new int[]{7, 8, 9, 11, 12}));
    }
}

Output

4
4 1

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

Optimal: put each value at its own index

The array itself can be the hash table. Only values in 1 to n matter, and value v has a natural home: index v - 1. Swap every such value into its home. Afterwards, the first index i with nums[i] != i + 1 gives the answer i + 1.

Text

[3, 2, -1, 1]
i = 0: 3 goes to index 2  ->  [-1, 2, 3, 1]    -1 has no home, move on
i = 1: 2 is home
i = 2: 3 is home
i = 3: 1 goes to index 0  ->  [1, 2, 3, -1]    -1 has no home, move on
first mismatch: index 3  ->  answer 4

Java

public class Main {
    static int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            // Keep swapping until nums[i] has no home or its home already holds the right value.
            while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                int home = nums[i] - 1;
                int tmp = nums[i];
                nums[i] = nums[home];
                nums[home] = tmp;
            }
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) return i + 1;
        }
        return n + 1;
    }

    public static void main(String[] args) {
        System.out.println(firstMissingPositive(new int[]{2, 3, -7, 6, 8, 1, -10, 15}));
        System.out.println(firstMissingPositive(new int[]{3, 2, -1, 1}) + " " + firstMissingPositive(new int[]{7, 8, 9, 11, 12}));
        System.out.println(firstMissingPositive(new int[]{1, 1}) + " " + firstMissingPositive(new int[]{1, 2, 3}));
    }
}

Output

4
4 1
2 4

Time: O(n): every swap puts one value into its home for good, so there are at most n swaps in total. Space: O(1).

The check nums[home] != nums[i] stops the loop on duplicates: in [1, 1], the second 1 would otherwise swap with the first forever.

Edge cases

No positives: the answer is 1.
All of 1 to n present: the answer is n + 1.
Mutating the input: this version reorders the array. Copy it first if the caller needs the original order.