41. First Missing Positive - Explanation

Description

You are given an unsorted integer array nums. Return the smallest positive integer that is not present in nums.

You must implement an algorithm that runs in O(n) time and uses O(1) auxiliary space.

Example 1:

Input: nums = [-2,-1,0]

Output: 1

Example 2:

Input: nums = [1,2,4]

Output: 3

Example 3:

Input: nums = [1,2,4,5,6,3,1]

Output: 7

Constraints:

1 <= nums.length <= 100,000
-(2^31) <= nums[i] <= ((2^31)-1)

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

Intuition

The simplest way to find the first missing positive is to just check each positive integer one by one.
We start with 1, scan the entire array looking for it, and if we find it, move on to 2, then 3, and so on.
The first number we can't find in the array is our answer.

This works because we're guaranteed the answer exists somewhere between 1 and n + 1 (where n is the array size). In the worst case, if the array contains exactly [1, 2, 3, ..., n], the answer would be n + 1.

Algorithm

Start with missing = 1.
Search the entire array for missing.
If found, increment missing and repeat.
If not found, return missing.

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        missing = 1
        while True:
            flag = True
            for num in nums:
                if missing == num:
                    flag = False
                    break

            if flag:
                return missing
            missing += 1

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(1)$

2. Boolean Array

Intuition

Here's a key observation: if the array has n elements, the answer must be in the range [1, n + 1].
Why? Because even if the array contains n distinct positive integers, they can at most cover 1 through n, making n + 1 the answer.

So we only care about numbers from 1 to n. We can create a boolean array of size n where seen[i] tells us whether i + 1 exists in the input. Then we just find the first index that's still false.

Algorithm

Create a boolean array seen of size n, initialized to false.
For each number in the input:
- If it's between 1 and n, mark seen[num - 1] = true.
Scan seen from index 0 to n - 1:
- Return i + 1 for the first false entry.
If all entries are true, return n + 1.

class Solution:
    def firstMissingPositive(self, nums: list[int]) -> int:
        n = len(nums)
        seen = [False] * n
        for num in nums:
            if num > 0 and num <= n:
                seen[num - 1] = True

        for num in range(1, n + 1):
            if not seen[num - 1]:
                return num

        return n + 1

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

3. Sorting

Intuition

If the array is sorted, finding the first missing positive becomes straightforward.
We walk through the sorted array while tracking the smallest positive integer we're looking for.
Whenever we see that number, we increment our target. The first target we don't find is the answer.

We skip negative numbers and zeros since they don't affect our search. Duplicates are also handled naturally since we only increment when we find an exact match.

Algorithm

Sort the array.
Initialize missing = 1.
For each number in the sorted array:
- If num is positive and equals missing, increment missing.
Return missing.

class Solution:
    def firstMissingPositive(self, nums: list[int]) -> int:
        nums.sort()
        missing = 1
        for num in nums:
            if num > 0 and missing == num:
                missing += 1
        return missing

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(1)$ or $O(n)$ depending on the sorting algorithm.

4. Negative Marking

Intuition

Can we achieve O(1) space without sorting? Yes, by using the input array itself as our hash map.

The idea is to use the sign of each element as a flag. If the value at index i is negative, it means i + 1 exists in the array. But there's a catch: the array might already contain negative numbers or zeros, which would interfere with our marking scheme.

So we first convert all non-positive numbers to 0. Then for each value v in the range [1, n], we mark the element at index v - 1 as negative. If it's already 0, we use a special marker -(n + 1) to indicate presence while keeping it distinguishable.

Finally, the first non-negative index tells us which number is missing.

Algorithm

Replace all negative numbers with 0.
For each number val (using absolute value to handle already-marked cells):
- If 1 <= val <= n:
  - If nums[val - 1] > 0, negate it.
  - If nums[val - 1] == 0, set it to -(n + 1).
Find the first index where nums[i] >= 0 and return i + 1.
If no such index exists, return n + 1.

class Solution:
    def firstMissingPositive(self, nums: list[int]) -> int:
        for i in range(len(nums)):
            if nums[i] < 0:
                nums[i] = 0

        for i in range(len(nums)):
            val = abs(nums[i])
            if 1 <= val <= len(nums):
                if nums[val - 1] > 0:
                    nums[val - 1] *= -1
                elif nums[val - 1] == 0:
                    nums[val - 1] = -1 * (len(nums) + 1)

        for i in range(1, len(nums) + 1):
            if nums[i - 1] >= 0:
                return i

        return len(nums) + 1

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ extra space.

5. Cycle Sort

Intuition

Another way to use the array as its own hash map is through cycle sort. The goal is to place each number at its "correct" index: value 1 at index 0, value 2 at index 1, and so on.

We iterate through the array, and for each element, if it's a valid positive number in range [1, n] and not already in its correct position, we swap it to where it belongs. We keep swapping until the current position holds the right value or an out-of-range number.

After this rearrangement, we scan the array. The first position where nums[i] != i + 1 gives us the missing number.

Algorithm

Iterate through the array with index i:
- While nums[i] is in range [1, n] and nums[i] != nums[nums[i] - 1]:
  - Swap nums[i] with nums[nums[i] - 1].
Scan the array:
- Return i + 1 for the first index where nums[i] != i + 1.
If all positions are correct, return n + 1.

class Solution:
    def firstMissingPositive(self, nums: list[int]) -> int:
        n = len(nums)
        i = 0
        while i < n:
            if nums[i] <= 0 or nums[i] > n:
                i += 1
                continue

            index = nums[i] - 1
            if nums[i] != nums[index]:
                nums[i], nums[index] = nums[index], nums[i]
            else:
                i += 1

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

        return n + 1

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ extra space.