First missing positive

Hard TimeO(n) SpaceO(1)

Given an unsorted array nums, return the smallest positive integer that does not appear in it. The array may hold negatives, zeros and duplicates, and with n values the answer is always one of 1…n+1.

Examples

Example 1

Input
nums = [3, 4, -1, 1]
Output
2
1 is there and 2 is not, so 2 is the smallest positive missing.

Example 2

Input
nums = [1, 2, 3]
Output
4
1, 2 and 3 are all present, so the answer is one past the end.

The Code

function firstMissingPositive(nums) {
  const n = nums.length;
  for (let i = 0; i < n; i++) {
    while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] !== nums[i]) {
      const target = nums[i] - 1;
      const temp = nums[target];
      nums[target] = nums[i];
      nums[i] = temp;
    }
  }
  for (let i = 0; i < n; i++) {
    if (nums[i] !== i + 1) return i + 1;
  }
  return n + 1;
}
firstMissingPositive([3, 4, -1, 1]);
Done
Step through firstMissingPositive([3, 4, -1, 1]) call by call

Explanation

With n slots, the answer cannot be larger than n + 1: either all of 1…n are present, and the answer is n + 1, or one of them is missing. So put each of those values where it would sit in a sorted array — value v at position v − 1 — and the question becomes which position is holding the wrong thing. Every value that gets moved lands where it belongs and is never moved again, so all the rearranging together costs one pass over the array.

  1. 1

    A value v belongs at index v − 1. At i = 0, nums[0] is 3, which belongs at index 2 — where a −1 sits — so the two swap.

    i
    −1
    0
    4
    1
    3
    2
    1
    3

    nums[i]=3belongs at=index 2

    swap 0 and 2 → [−1, 4, 3, 1]

  2. 2

    i is still 0, and the value that swapped in is −1 — outside 1…4, so the while stops and i moves on. At i = 1, nums[1] is 4, which belongs at index 3, where a 1 sits.

    -1
    0
    i
    1
    1
    3
    2
    4
    3

    nums[i]=4belongs at=index 3

    swap 1 and 3 → [−1, 1, 3, 4]

  3. 3

    That swap brought a 1 to index 1, and 1 belongs at index 0 — where the −1 is. The while turns again and swaps them.

    1
    0
    i
    −1
    1
    3
    2
    4
    3

    nums[i]=1belongs at=index 0

    swap 1 and 0 → [1, −1, 3, 4]

  4. 4

    Now nums[1] is −1, which is outside 1…4, so nothing more is placed. Every value that could matter — the 1, the 3 and the 4 — is already at its own index.

    1
    0
    -1
    1
    i
    3
    2
    4
    3

    nums[i]=−1

    −1 not in 1…4 → left alone

  5. 5

    The second loop asks each index whether it holds i + 1. Index 0 holds 1, which is right. Index 1 holds −1 rather than 2 — the first index holding the wrong thing, so 2 is returned.

    1
    0
    i
    -1
    1
    3
    2
    4
    3

    nums[i]=−1

    nums[1] ≠ 2 → return 2

More like this

All arrays & loops examples (10) →