First Missing Positive

Problem

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 constant extra space.

 

Example 1:

Input: nums = [1,2,0]
Output: 3

Example 2:

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

Example 3:

Input: nums = [7,8,9,11,12]
Output: 1

 

Constraints:

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

Solution

/**
 * @param {number[]} nums
 * @return {number}
 */
var firstMissingPositive = function(nums) {
    // for nums[i] = n, set nums[n - 1] = n (use nums as a set)
    for (let i = 0; i < nums.length; i++) {
        const n = nums[i];
        // n is in range and has not been processed before
        if ((nums[n - 1] ?? n) !== n) {
            nums[i] = nums[n - 1]; // swap elements
            nums[n - 1] = n;
            if (n !== i + 1) { // need to process swapped element
                i--;
            }
        }
    }

    // find index where nums[i] !== i + 1
    nums.push(0)
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] !== i + 1) {
            return i + 1;
        }
    }
};

Let nums contain l elements. Then by the pigeonhole principle, the first missing positive must be in the range of [1, l + 1] (ie. nums can hold at most [1, l] unique consecutive positive values starting from 1). Thus, we can use nums as a set, where for all value n that is in range of [1, l], set nums[n - 1] = n. This means, as we iterate through nums a second time, the first i + 1 where nums[i] !== i + 1 is the smallest missing positive.