First Missing Positive

return missing positive number

First Missing Positive

Problem

You are given an unsorted integer array nums. Return the smallest positive integer that is not in nums.

Your algorithm must run in O(n) time and use O(1) extra space.

Examples

Example 1

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

• The numbers 1 and 2 are in the array.
• The next number, 3, is missing.

Example 2

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

• 1 is in the array, but 2 is missing.

Example 3

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

• The smallest positive number, 1, is missing.

Constraints

• 1 <= nums.length <= 10^5
• -2^31 <= nums[i] <= 2^31 - 1

Main Idea

If the array has n numbers, the answer is always between 1 and n + 1.

• If the array has all of 1, 2, ..., n, the answer is n + 1.
• Otherwise, one number between 1 and n is missing, and the smallest missing one is the answer.

So numbers that are <= 0 or > n do not matter. We only care about numbers from 1 to n.

Solution 1: Using a Set

First we put all numbers in a Set. Then we check 1, 2, 3, ... one by one until we find a number that is not in the set.

var firstMissingPositive = function (nums) {
    let set = new Set(nums);
    let max = Math.max(...nums);

    // check every number from 1 to max
    for (let i = 1; i <= Math.max(max, 1); i++) {
        if (!set.has(i)) {
            return i;
        }
    }

    // all numbers from 1 to max are present
    return max + 1;
};

How the Code Works

• set stores all numbers, so we can check "is this number here?" in O(1) time.
• max is the biggest number in the array.
• We check numbers from 1 up to max. The first number not in the set is the answer.
• If the loop ends, every number from 1 to max is present, so the answer is max + 1.
• If max is 0 or negative, Math.max(max, 1) makes the loop check 1. It is not in the set, so we return 1.

Complexity

• Time Complexity: O(n)
  • Building the set takes O(n).
  • The loop runs up to max times. In the worst case this can be bigger than n, but it stops at the first missing number, and there can be at most n + 1 checks before that happens.
• Space Complexity: O(n)
  • The set stores up to n numbers.

Important: This solution does not meet the problem rule. The problem asks for O(1) extra space, but the set uses O(n). It is a good first solution, but the next one is the one the problem wants.

Tip: Math.max(...nums) passes every number as an argument. With very large arrays, this can cause a "Maximum call stack size exceeded" error. A simple loop to find the max is safer.

Solution 2: Place Each Number at Its Correct Index (O(1) Space)

The idea is to use the array itself as a hash table.

• The number 1 should be at index 0.
• The number 2 should be at index 1.
• In general, the number x should be at index x - 1.

We move each number to its correct place. After that, we scan the array. The first index i where nums[i] !== i + 1 tells us that i + 1 is missing.

Steps

• For each index i, look at nums[i].
• While nums[i] is between 1 and n, and it is not already at its correct place, swap it to its correct place.
• Ignore numbers that are <= 0 or > n.
• After all swaps, scan the array. The first index i with nums[i] !== i + 1 gives the answer i + 1.
• If every index is correct, the answer is n + 1.

Code

var firstMissingPositive = function (nums) {
    let n = nums.length;

    for (let i = 0; i < n; i++) {
        // keep moving nums[i] until it is in the right place
        // or it is a number we do not care about
        while (
            nums[i] >= 1 &&
            nums[i] <= n &&
            nums[nums[i] - 1] !== nums[i]
        ) {
            let correctIndex = nums[i] - 1;

            // swap nums[i] with the number at its correct index
            let temp = nums[correctIndex];
            nums[correctIndex] = nums[i];
            nums[i] = temp;
        }
    }

    // find the first place where the number is wrong
    for (let i = 0; i < n; i++) {
        if (nums[i] !== i + 1) {
            return i + 1;
        }
    }

    // all numbers from 1 to n are present
    return n + 1;
};

How the Code Works

Step 1: Move numbers to their correct place

• nums[i] >= 1 && nums[i] <= n means the number is useful. Only these numbers can be the answer's neighbors.
• nums[nums[i] - 1] !== nums[i] checks that the correct place does not already hold the same number.
  • This check also stops the loop when there are duplicates. Without it, two equal numbers would swap forever.
• Inside the loop, we save correctIndex first, and then swap with a temp variable.
  • We save correctIndex before the swap, because nums[i] changes during the swap.

Step 2: Scan for the first wrong place

• After Step 1, every useful number sits at its correct index.
• The first index where nums[i] !== i + 1 means the number i + 1 is missing.

Step 3: Return n + 1

• If no index is wrong, then 1 to n are all present. So the answer is n + 1.

Dry Run

Let us take nums = [3, 4, -1, 1]. Here n = 4.

Now we scan the array:

• Index 0 has 1. This is correct.
• Index 1 has -1, but it should be 2. So the answer is 2.

Complexity

• Time Complexity: O(n)
  • The while loop is inside a for loop, so it may look like O(n²).
  • But each swap puts one number in its final correct place, and that number is never moved again.
  • So there are at most n swaps in total, and the scan at the end takes O(n).
• Space Complexity: O(1)
  • We only use a few variables. We reuse the input array, so there is no extra table.

Note: This solution changes the input array. If you must keep the original array, you need to make a copy, which costs O(n) space.

Comparison

Summary

• The answer is always in the range 1 to n + 1, where n is the length of the array.
• The Set solution is easy and runs in O(n) time, but it uses O(n) space. So it does not follow the problem rule.
• The best solution uses the array as a hash table. The number x belongs at index x - 1.
  • We swap each useful number to its correct place.
  • We ignore numbers that are <= 0 or > n.
  • The first index where nums[i] !== i + 1 gives the answer i + 1.
  • If all places are correct, the answer is n + 1.
• The duplicate check nums[nums[i] - 1] !== nums[i] stops infinite swaps.
• The best solution runs in O(n) time and uses O(1) space.