First Missing Positive – Solution & Complexity

Q: What is the time and space complexity of First Missing Positive?

The optimal First Missing Positive solution runs in `O(n)` time and `O(1)` space. Place each in-range value x at index x-1 by swapping, then scan for the first index whose value is wrong.

Q: What is the most efficient way to solve First Missing Positive?

Place each in-range value x at index x-1 by swapping, then scan for the first index whose value is wrong. This gives `O(n)` time complexity, and is a classic arrays, in place, and cyclic sort problem.

Q: How do you solve First Missing Positive in Python, JavaScript, Java, Go, Rust, C++ & Ruby?

We provide a worked First Missing Positive solution in Python, JavaScript, Java, Go, Rust, C++ & Ruby with a step-by-step explanation above. You can also open the interactive editor to write and run your own Python solution against the test cases in the browser.

Q: Is First Missing Positive an easy or hard interview question?

First Missing Positive is generally rated **Hard**. It tests arrays, in place, and cyclic sort, which are common coding-interview patterns.

Solution Walkthrough

Step 1: Understand what actually matters
- The answer must be in the range 1..n+1 for an array of length n.
- Negative numbers, zeros, and values larger than n cannot directly block the first missing positive.
Step 2: Start with a set-based brute-force solution
- Insert every value into a hash set.
- Then scan upward from 1 until you find the first positive missing from the set.
- This is easy to reason about, but it costs O(n) extra space.
def first_missing_positive(nums: list[int]) -> int: seen = set(nums) candidate = 1 while candidate in seen: candidate += 1 return candidate
Step 3: Place each value where it belongs
- Value 1 belongs at index 0, value 2 at index 1, and so on.
- If we keep swapping each in-range value into its correct slot, the first index that disagrees with this rule reveals the answer.

Step 4: Use cyclic placement for O(1) extra space

While a value is in the range 1..n and not already in its correct slot, swap it into position value - 1.
After that placement phase, scan left to right for the first index whose value is wrong.

def first_missing_positive(nums: list[int]) -> int:
    i = 0
    n = len(nums)
    while i < n:
        correct = nums[i] - 1
        if 1 <= nums[i] <= n and nums[correct] != nums[i]:
            nums[i], nums[correct] = nums[correct], nums[i]
        else:
            i += 1

    for index, value in enumerate(nums):
        if value != index + 1:
            return index + 1
    return n + 1

Step 5: Dry run / placement trace

Trace nums = [3,4,-1,1].

step	array	explanation
start	`[3,4,-1,1]`	`3` belongs at index `2`
swap	`[-1,4,3,1]`	put `3` into its slot
skip	`[-1,4,3,1]`	`-1` is out of range, so move on
swap	`[-1,1,3,4]`	`4` belongs at index `3`
swap	`[1,-1,3,4]`	then `1` belongs at index `0`
scan	`[1,-1,3,4]`	index `1` should contain `2`, so the answer is `2`

Step 6: Common mistakes and follow-ups
- Forgetting to keep swapping until the current slot is either invalid or correct.
- Accessing nums[correct] before checking that the value is in the range 1..n.
- Using a clone in a context where the interviewer asked specifically for true O(1) extra space.
- Follow-up: can you solve the same problem with sign marking after first normalizing out-of-range values?
Step 7: Edge cases to test mentally
- Arrays containing only negatives should return 1.
- [1,2,3] should return 4.
- Duplicates like [1,1] still return 2.
- A single [1] should return 2, while a single [2] should return 1.

Step 8: Final full solution and complexity

Cyclic placement visits each index a constant number of times, so the optimal approach runs in O(n) time with O(1) extra space beyond the returned integer.

def first_missing_positive(nums: list[int]) -> int:
    i = 0
    n = len(nums)
    while i < n:
        correct = nums[i] - 1
        if 1 <= nums[i] <= n and nums[correct] != nums[i]:
            nums[i], nums[correct] = nums[correct], nums[i]
        else:
            i += 1

    for index, value in enumerate(nums):
        if value != index + 1:
            return index + 1
    return n + 1

First Missing Positive – Solution & Complexity

Solution Walkthrough

Step 1: Understand what actually matters

Step 2: Start with a set-based brute-force solution

Step 3: Place each value where it belongs

Step 4: Use cyclic placement for O(1) extra space

Step 5: Dry run / placement trace

Step 6: Common mistakes and follow-ups

Step 7: Edge cases to test mentally

Step 8: Final full solution and complexity

FAQ

What is the time and space complexity of First Missing Positive?

What is the most efficient way to solve First Missing Positive?

How do you solve First Missing Positive in Python, JavaScript, Java, Go, Rust, C++ & Ruby?

Is First Missing Positive an easy or hard interview question?

See also

First Missing Positive – Solution & Complexity

Solution Walkthrough

1Step 1: Understand what actually matters

2Step 2: Start with a set-based brute-force solution

3Step 3: Place each value where it belongs

4Step 4: Use cyclic placement for O(1) extra space

5Step 5: Dry run / placement trace

6Step 6: Common mistakes and follow-ups

7Step 7: Edge cases to test mentally

8Step 8: Final full solution and complexity

FAQ

What is the time and space complexity of First Missing Positive?

What is the most efficient way to solve First Missing Positive?

How do you solve First Missing Positive in Python, JavaScript, Java, Go, Rust, C++ & Ruby?

Is First Missing Positive an easy or hard interview question?

See also

Step 1: Understand what actually matters

Step 2: Start with a set-based brute-force solution

Step 3: Place each value where it belongs

Step 4: Use cyclic placement for O(1) extra space

Step 5: Dry run / placement trace

Step 6: Common mistakes and follow-ups

Step 7: Edge cases to test mentally

Step 8: Final full solution and complexity