Skip to content
ReadMe Daily

Search articles, problems, patterns and every cheat sheet topic.

First Missing Positive

Find the smallest positive whole number missing from an unsorted array in O(n) time and O(1) extra space by using the array itself as a hash table.

Updated Medium read: 7 min read

Approaches at a glance

ApproachTimeSpace
Hash setO(n)O(n)
The array as its own hash tableO(n)O(1)

The problem

Given an unsorted array of integers, return the smallest positive whole number (1, 2, 3 and so on) that does not appear in it. The array may contain negative numbers, zeros and repeats. The solution must run in O(n) time and use only constant extra space.

[1, 2, 0]           →  3
[3, 4, -1, 1]       →  2
[7, 8, 9, 11, 12]   →  1
[]                  →  1

The two requirements together are what make this hard. Each one alone is easy:

  • Sorting first uses no extra space, but takes O(n log n) time.
  • A hash set takes O(n) time, but uses O(n) extra space.

One fact that shrinks the problem

For an array of length n, the answer is always between 1 and n + 1.

The answer is the first gap in the sequence 1, 2, 3 and so on. To push that gap as far out as possible, the array would have to contain 1, 2, 3 up to n, using every slot, and then the answer is n + 1. Any other contents waste at least one slot on something outside 1 to n, or on a repeat, which leaves a gap somewhere in 1 to n.

Two things follow. Values that are zero, negative or larger than n can never affect the answer, so they can be ignored. And there are only n values worth tracking, which happens to be exactly the number of slots in the array.

Approach 1: hash set

Put everything in a set, then count up from 1 until a number is not there.

JavaScript

function firstMissingPositiveWithSet(numbers) {
  const present = new Set(numbers);
  let candidate = 1;
  while (present.has(candidate)) candidate++;
  return candidate;
}

Python

def first_missing_positive_with_set(numbers):
    present = set(numbers)
    candidate = 1
    while candidate in present:
        candidate += 1
    return candidate

By the fact above, the loop stops by n + 1 at the latest.

Time O(n): building the set and counting up are each at most about n steps. Space O(n) for the set, which breaks the space rule.

Approach 2: the array as its own hash table

A hash set answers one question: "is this value present?" For values from 1 to n, the array can answer that question itself, with a very simple hash function: value v belongs at index v − 1. So 1 lives at index 0, 2 at index 1, and so on.

If every value in range is moved to its home slot, then afterwards "is v present?" becomes "does index v − 1 hold v?". The first slot holding the wrong value marks the missing number.

The rearranging is done by swapping. For each position, look at the value there. If it is in the range 1 to n and not already at home, swap it into its home slot. The swap brings a different value back to the current position, so look again, and repeat until the value there is out of range or already at home.

JavaScript

function firstMissingPositive(numbers) {
  const n = numbers.length;
 
  for (let i = 0; i < n; i++) {
    // Keep swapping until the value at i is out of range or already at home.
    while (
      numbers[i] >= 1 &&
      numbers[i] <= n &&
      numbers[numbers[i] - 1] !== numbers[i]
    ) {
      const home = numbers[i] - 1;
      [numbers[i], numbers[home]] = [numbers[home], numbers[i]];
    }
  }
 
  for (let i = 0; i < n; i++) {
    if (numbers[i] !== i + 1) return i + 1;
  }
  return n + 1;
}

Python

def first_missing_positive(numbers):
    n = len(numbers)
 
    for i in range(n):
        # Keep swapping until the value at i is out of range or already at home.
        while (
            1 <= numbers[i] <= n
            and numbers[numbers[i] - 1] != numbers[i]
        ):
            home = numbers[i] - 1
            numbers[i], numbers[home] = numbers[home], numbers[i]
 
    for i in range(n):
        if numbers[i] != i + 1:
            return i + 1
    return n + 1

This rearranges the caller's array. That is the price of constant space, and it is worth saying aloud in an interview.

Walkthrough

[3, 4, -1, 1], so n = 4:

i Value at i Its home index Action Array after
0 3 2, which holds -1 Swap [-1, 4, 3, 1]
0 -1 out of range Move on [-1, 4, 3, 1]
1 4 3, which holds 1 Swap [-1, 1, 3, 4]
1 1 0, which holds -1 Swap [1, -1, 3, 4]
1 -1 out of range Move on [1, -1, 3, 4]
2 3 2, already home Move on [1, -1, 3, 4]
3 4 3, already home Move on [1, -1, 3, 4]

The second pass then checks each slot: index 0 holds 1, which is right; index 1 holds -1 where 2 should be. The answer is 2.

Space O(1): only a few variables besides the input.

Why this is O(n) despite the nested loop

A while inside a for looks like O(n²). It is not, because of what each swap achieves: every swap puts one value into its home slot for good. A value at home is never moved again, since the loop condition refuses to swap a value that is already where it belongs, and refuses to swap anything into a slot that already holds its correct value.

There are only n slots, so there can be at most n swaps over the entire run, however they are spread across the outer loop. Add the n steps of the outer loop itself and the total is about 2n.

Why the condition compares values, not positions

The swap condition is numbers[numbers[i] - 1] !== numbers[i]: "the home slot does not already hold this value". A more obvious test would be numbers[i] !== i + 1: "this value is not at home". That version hangs on repeats.

Take [1, 1]. At i = 1 the value is 1 and its home is index 0. It is not at home, so the obvious test says swap. But index 0 already holds a 1, so the swap exchanges two identical values, nothing changes, and the loop runs for ever. Comparing with what is in the home slot stops this: the home already has the right value, so the repeat is left where it is, and the second pass correctly reports 2.

Another way to use the array as its own table is to mark presence by sign: first replace every out-of-range value with n + 1, then for each value v make the number at index v − 1 negative. A slot that is still positive at the end marks a missing value. It makes the same trade as the swapping method, and is the usual approach when the values are already known to lie between 1 and n, as in LeetCode 448.

Try it yourself

Copy a solution from above, add the lines below, and run it. For JavaScript, paste both into the browser console, or save them in a file and run it with node. For Python, save them in a file and run it with python.

JavaScript

console.log(firstMissingPositive([3, 4, -1, 1])); // 2
console.log(firstMissingPositive([1, 2, 0])); // 3
console.log(firstMissingPositive([7, 8, 9, 11, 12])); // 1

Python

print(first_missing_positive([3, 4, -1, 1]))  # 2
print(first_missing_positive([1, 2, 0]))  # 3
print(first_missing_positive([7, 8, 9, 11, 12]))  # 1

The comment after each line is the result you should see.

Common mistakes

  • Using if instead of while for the swap. The value that arrives at position i after a swap may also need moving. A single swap leaves it stranded, as rows 3 and 4 of the walkthrough show.
  • Testing numbers[i] !== i + 1. This loops for ever when the array contains repeats.
  • Writing the swap in the wrong order. With a temporary variable, the home index must be worked out before numbers[i] is overwritten, or the second assignment uses the new value as its index.
  • Forgetting the final return n + 1. When the array is exactly 1 to n, every slot is correct and the answer lies just beyond the end.
  • Starting the count at 0. Zero is not positive. The smallest possible answer is 1, including for an empty array.

Original problem: LeetCode 41: First Missing Positive