Hard
ArrayHash Table
Updated Sep 2026

First Missing Positive

Asked at Netflix, Oracle, Walmart

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 O(1) extra space.

Asked At

CompanyDifficulty
NetflixHardView all Netflix questions →
OracleHardView all Oracle questions →
WalmartHardView all Walmart questions →

How to Think About It

1.

Brute force: for each number from 1 upward, check if it exists in the array using a hash set. Return the first one not found. Time: O(n^2), space: O(n).

2.

Better: use a hash set to store all numbers. Then iterate from 1 upward and return the first number not in the set. Time: O(n), space: O(n). But the problem requires O(1) space.

3.

Sorting approach: sort the array, then scan for the first gap. Time: O(n log n), space: O(1) (in-place sort). But the problem requires O(n) time.

4.

Cyclic sort (optimal): the key insight is that the answer must be in the range [1, n+1] where n is the array length. Place each number in its "correct" position: number i should be at index i-1. Iterate through the array and swap each number to its correct position if it is in [1, n] and not already in place. Then scan for the first position where the value doesn't match.

5.

Visual walkthrough for [3, 4, -1, 1]:
n=4. Answer must be in [1, 5].
i=0: nums[0]=3. Correct position is index 2. Swap: nums=[-1,4,3,1].
i=0: nums[0]=-1. Not in [1,4]. Skip.
i=1: nums[1]=4. Correct position is index 3. Swap: nums=[-1,1,3,4].
i=1: nums[1]=1. Correct position is index 0. Swap: nums=[1,-1,3,4].
i=1: nums[1]=-1. Not in [1,4]. Skip.
i=2: nums[2]=3. Correct position is index 2. Already in place. Skip.
i=3: nums[3]=4. Correct position is index 3. Already in place. Skip.
Scan: index 0 has 1 (correct), index 1 has -1 (should be 2). Answer: 2.

6.

Time: O(n) — each element is swapped at most once. Space: O(1) — in-place swaps only. This is the optimal solution.

Optimal Approach

Cyclic sort:

  1. For each index i from 0 to n-1:
    • While nums[i] is in [1, n] and nums[i] != nums[nums[i] - 1]: swap nums[i] with nums[nums[i] - 1].
  2. Scan the array: find the first index i where nums[i] != i + 1. Return i + 1.
  3. If all positions are correct, return n + 1.

Walkthrough: [3, 4, -1, 1]

  • i=0: nums[0]=3, swap with nums[2]: [-1, 4, 3, 1]. nums[0]=-1, skip.
  • i=1: nums[1]=4, swap with nums[3]: [-1, 1, 3, 4]. nums[1]=1, swap with nums[0]: [1, -1, 3, 4]. nums[1]=-1, skip.
  • i=2: nums[2]=3, correct. Skip.
  • i=3: nums[3]=4, correct. Skip.
  • Scan: nums[0]=1 (ok), nums[1]=-1 (should be 2). Return 2.

Time: O(n). Space: O(1).

What Trips People Up in Real Interviews

1.

Using a hash set when the problem requires O(1) space. The hash set approach is O(n) space. Always mention it as an alternative, then optimize to cyclic sort.

2.

The swap condition must check three things: (1) nums[i] is in [1, n], (2) nums[i] is not already in its correct position. Missing any condition causes an infinite loop or incorrect result.

3.

Confusing the index-value relationship. Number i should be at index i-1 (0-indexed). So the correct position for value v is index v-1. Many candidates use index v, which is off by one.

4.

Not using a while loop for the swap. A single if-then-swap is not enough because after swapping, the new value at position i might also need to be swapped. The while loop continues until the current position is correct or the value is out of range.

5.

Forgetting to handle the case where all positions are correct. After the scan, if every nums[i] == i + 1, the answer is n + 1. This happens when the array is a permutation of [1, n].

Solution Code

def firstMissingPositive(nums):
    n = len(nums)
    for i in range(n):
        while 1 <= nums[i] <= n and nums[i] != nums[nums[i] - 1]:
            nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1
    return n + 1

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the 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 `O(1)` extra space.

How do you solve First Missing Positive?

The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.

What companies ask First Missing Positive?

First Missing Positive is asked at Netflix, Oracle, Walmart. It is a hard difficulty problem.

What are common mistakes on First Missing Positive?
  • Using a `hash set` when the problem requires `O(1)` space. The `hash set` approach is `O(n)` space. Always mention it as an alternative, then optimize to cyclic sort.
  • The swap condition must check three things: (1) `nums[i]` is in [1, n], (2) `nums[i]` is not already in its correct position. Missing any condition causes an infinite loop or incorrect result.
  • Confusing the index-value relationship. Number i should be at index i-1 (0-indexed). So the correct position for value v is index v-1. Many candidates use index v, which is off by one.
  • Not using a while loop for the swap. A single if-then-swap is not enough because after swapping, the new value at position i might also need to be swapped. The while loop continues until the current position is correct or the value is out of range.
  • Forgetting to handle the case where all positions are correct. After the scan, if every `nums[i] == i + 1`, the answer is `n + 1`. This happens when the array is a permutation of [1, n].