First Missing Positive

You are given an unsorted integer array nums, which may contain negative numbers, zeros and repeated values.

Return the smallest positive integer (1, 2, 3, ...) that does not appear anywhere in nums.

Aim for a solution that runs in O(n) time and uses only a constant amount of extra memory. You are allowed to rearrange or overwrite the contents of nums while you work.

Example 1

Example 2

Example 3

Constraints

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

Pattern Path · Hashing & Counting · problem 14 of 169

Start simple

Sort the array and walk it looking for the first gap (O(n log n)), or put every value in a hash set and test 1, 2, 3, ... (O(n) time but O(n) extra space).

The key idea

The key observation is a bound: an array of length n can contain at most n distinct positive values, so among 1, 2, ..., n + 1 at least one is missing. The answer is therefore in [1, n + 1], and any value outside 1..n is irrelevant.

That bound means the array itself is big enough to act as a presence table: let slot v - 1 be the "home" of value v. Walk through the array; while the current value v is in range and its home does not already hold v, swap it home. The value that comes back gets the same treatment. The check nums[v - 1] != v also stops endless swapping on duplicates.

Each swap places a value in its home permanently, so there are at most n swaps in total; the nested loop is still O(n) overall. Afterwards, scan from the left: the first index i where nums[i] != i + 1 means i + 1 never appeared. If every slot is correct, the array holds exactly 1..n and the answer is n + 1.

Complexity

• Time: O(n)
• Space: O(1) extra (the input array is reused)

Python

class Solution:
    def firstMissingPositive(self, nums):
        n = len(nums)
        # Only 1..n can be the answer's competitors, so try to put each such
        # value v into its "home" slot nums[v - 1] by swapping.
        for i in range(n):
            while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
                home = nums[i] - 1
                nums[i], nums[home] = nums[home], nums[i]

        # The first slot that does not hold its own value reveals the gap.
        for i in range(n):
            if nums[i] != i + 1:
                return i + 1
        return n + 1

JavaScript

var firstMissingPositive = function(nums) {
  const n = nums.length;
  // Only 1..n can be the answer's competitors, so try to put each such
  // value v into its "home" slot nums[v - 1] by swapping.
  for (let i = 0; i < n; i++) {
    while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] !== nums[i]) {
      const home = nums[i] - 1;
      [nums[i], nums[home]] = [nums[home], nums[i]];
    }
  }

  // The first slot that does not hold its own value reveals the gap.
  for (let i = 0; i < n; i++) {
    if (nums[i] !== i + 1) return i + 1;
  }
  return n + 1;
};

What the interviewer is checking

The interviewer wants to see you derive the 1..n+1 bound and then reuse the input as a hash table, while proving the nested swap loop is still linear.

Mistakes to avoid

• Looping forever on duplicates by swapping a value with an identical copy; check the destination, not just the index.
• Forgetting the case where 1..n are all present, which must return n + 1.
• Indexing with values that are 0, negative or larger than n.
• Swapping in an order that reads the index after it has been overwritten (compute the home index first).

Follow-ups to expect

• Can you do it without swapping? (Mark presence by negating values.)
• What if the array is read-only? (Need O(n) space or O(n log n) time.)
• How would you find the k-th missing positive? (Same placement, count gaps.)

In real software

Allocators that hand out the smallest free ID, port number or file descriptor face the same question, and in-place index marking is how memory-tight systems answer it.

Practice next