First missing positive

Find the smallest positive integer that is not in the array. Swap every value 1..n into its home index v - 1, then the first index that holds the wrong value names the answer.

The idea

With n numbers, the answer is somewhere in 1..n + 1: n values cannot cover more than 1..n. So only values 1..n matter, and each has a natural home, index v - 1. Cyclic placement swaps every such value into its home; each swap settles one value for good, so there are at most n swaps in total. Afterwards index i holds i + 1 exactly when i + 1 is present, and the first index that does not is the answer.

Code

public int FirstMissingPositive(int[] nums) {
    int n = nums.Length;
    for (int i = 0; i < n; i++) {
        // stop when nums[i] is out of range, already home, or a duplicate
        while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
            int j = nums[i] - 1; // value v belongs at index v - 1
            (nums[i], nums[j]) = (nums[j], nums[i]);
        }
    }
    for (int i = 0; i < n; i++)
        if (nums[i] != i + 1) return i + 1;
    return n + 1; // 1..n are all present
}

Tips

• The check nums[nums[i] - 1] != nums[i] stops duplicates from swapping forever: if the home already holds the same value, leave this copy where it is.
• Negatives, zero and values above n are simply left in place. They end up in slots whose own value is missing, which is exactly what the scan reports.
• Try 1, 2, 3: every value is home, so the scan finds nothing and the answer is n + 1 = 4.

In the .NET library

The tuple swap (nums[i], nums[j]) = (nums[j], nums[i]) evaluates both right-hand values before assigning, so no temporary variable is needed. j must be computed first: writing nums[nums[i] - 1] inside the tuple would read nums[i] after it changed.