LeetCode 41: First Missing Positive

Problem Restatement

We are given an unsorted integer array nums.

We need to return the smallest positive integer that does not appear in the array.

The solution must run in O(n) time and use O(1) auxiliary space.

Examples:

nums = [1, 2, 0]

The positive integers 1 and 2 are present, so the smallest missing positive integer is 3.

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

The number 1 is present, but 2 is missing, so the answer is 2.

nums = [7, 8, 9, 11, 12]

The number 1 is missing, so the answer is 1.

Input and Output

The function shape is:

def firstMissingPositive(nums: list[int]) -> int:
    ...

Key Observation

Let n = len(nums).

The answer must be in the range:

1, 2, 3, ..., n + 1

Why?

If the array contains every number from 1 to n, then the smallest missing positive is n + 1.

Otherwise, at least one number from 1 to n is missing, and the smallest missing positive is inside that range.

So we only care about values from 1 to n.

Values like 0, negative numbers, and numbers greater than n cannot be the smallest missing positive.

First Thought: Use a Set

A simple solution is to put all numbers into a set.

Then check 1, 2, 3, and so on until we find the first number not in the set.

class Solution:
    def firstMissingPositive(self, nums: list[int]) -> int:
        seen = set(nums)

        x = 1
        while x in seen:
            x += 1

        return x

This is easy to understand.

The problem is space.

The set may store n numbers, so the space complexity is O(n). The problem asks for O(1) auxiliary space, so we need to use the input array itself.

Key Insight

For a number x in the range 1 <= x <= n, its natural position is index x - 1.

So:

We can rearrange the array in-place so that every useful number goes to its correct index.

After rearranging, if index i does not contain i + 1, then i + 1 is missing.

For example:

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

After placing valid numbers in their correct positions, we want something like:

[1, -1, 3, 4]

Index 0 has 1.

Index 1 should have 2, but it does not.

So the answer is 2.

Algorithm

Let n = len(nums).

First pass: rearrange the array.

For each index i, while nums[i] is a useful number and is not already in the correct place, swap it into its correct place.

A number is useful if:

1 <= nums[i] <= n

Its correct index is:

nums[i] - 1

We keep swapping while:

1 <= nums[i] <= n and nums[i] != nums[nums[i] - 1]

The second condition prevents infinite loops with duplicates.

For example, in:

nums = [1, 1]

The second 1 wants to go to index 0, but index 0 already contains 1. There is nothing useful to swap.

Second pass: find the first mismatch.

For each index i, if:

nums[i] != i + 1

then i + 1 is the smallest missing positive.

If every index is correct, return:

n + 1

Walkthrough

Use this input:

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

The length is 4, so we only care about numbers from 1 to 4.

Start:

[3, 4, -1, 1]

At index 0, the value is 3.

The correct index for 3 is 2.

Swap index 0 and index 2:

[-1, 4, 3, 1]

Now index 0 has -1, which is not useful.

At index 1, the value is 4.

The correct index for 4 is 3.

Swap index 1 and index 3:

[-1, 1, 3, 4]

Index 1 now has 1.

The correct index for 1 is 0.

Swap index 1 and index 0:

[1, -1, 3, 4]

Now the array has useful numbers in their correct places where possible.

Scan from left to right:

The first mismatch is at index 1.

So the answer is:

2

Correctness

Every positive integer x in the range 1 <= x <= n has exactly one correct position: index x - 1.

During the first pass, whenever such a number is not already represented at its correct position, we swap it closer to that position. The swap places x at index x - 1.

Duplicates are handled by the condition:

nums[i] != nums[nums[i] - 1]

If the correct position already contains the same value, then placing another copy there would not help. We stop swapping that value.

After the first pass, if a number x from 1 to n exists in the array, then one copy of x must be at index x - 1.

Therefore, during the second pass, the first index i where nums[i] != i + 1 means the value i + 1 is not present in the array.

Because we scan indices from left to right, this is the smallest missing positive integer.

If every index i contains i + 1, then all numbers from 1 to n are present. The smallest missing positive integer is therefore n + 1.

Complexity

Although the code has a nested while loop, the total number of swaps is bounded by O(n). Each successful swap places at least one useful number into its final position.

Implementation

class Solution:
    def firstMissingPositive(self, nums: list[int]) -> int:
        n = len(nums)

        for i in range(n):
            while 1 <= nums[i] <= n and nums[i] != nums[nums[i] - 1]:
                correct_index = nums[i] - 1
                nums[i], nums[correct_index] = nums[correct_index], nums[i]

        for i in range(n):
            if nums[i] != i + 1:
                return i + 1

        return n + 1

Code Explanation

We first store the array length:

n = len(nums)

Only values from 1 to n matter.

Then we scan every index:

for i in range(n):

At each index, we keep moving the current value while it is useful and not already represented at its correct position:

while 1 <= nums[i] <= n and nums[i] != nums[nums[i] - 1]:

The correct index for nums[i] is:

correct_index = nums[i] - 1

Then we swap:

nums[i], nums[correct_index] = nums[correct_index], nums[i]

After this rearrangement, we scan the array again:

for i in range(n):
    if nums[i] != i + 1:
        return i + 1

The first mismatch gives the smallest missing positive.

If there is no mismatch, the array contains all values from 1 to n, so the answer is:

return n + 1

Testing

def run_tests():
    s = Solution()

    assert s.firstMissingPositive([1, 2, 0]) == 3
    assert s.firstMissingPositive([3, 4, -1, 1]) == 2
    assert s.firstMissingPositive([7, 8, 9, 11, 12]) == 1
    assert s.firstMissingPositive([1]) == 2
    assert s.firstMissingPositive([2]) == 1
    assert s.firstMissingPositive([1, 1]) == 2
    assert s.firstMissingPositive([2, 2]) == 1
    assert s.firstMissingPositive([1, 2, 3, 4]) == 5
    assert s.firstMissingPositive([-1, -2, 0]) == 1
    assert s.firstMissingPositive([2, 1]) == 3

    print("all tests passed")

run_tests()