First Missing Positive

+10

You get an unsorted array of integers nums. Return the smallest positive integer (1 or larger) that does not appear in nums. The array may hold negative numbers, zeros, repeated values and values far larger than its length.

Function

firstMissingPositive(nums: integer-array) → integer

numsinteger-array: the unsorted integers, which may repeat and may be negative, zero or very large
Returnsinteger: the smallest positive integer that is missing from nums

Constraints

1 ≤ nums.length ≤ 10⁴
-10⁹ ≤ nums[i] ≤ 10⁹
The values are in no particular order and may repeat.

Examples

Input: nums = [5, -2, 1, 3, 2, 9]
Output: 4
Explanation: 1, 2 and 3 are all in the array and 4 is not, so the answer is 4. The 5 and the 9 do not matter once a smaller value is missing.

Follow-up

Can you find the answer in O(n) time while using only O(1) extra memory?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Sorting takes O(n log n) time and a hash set O(n) extra memory. A bound beats both: n values cover at most n of the numbers 1 to n+1, so the answer is at most n+1. Only the values 1 to n matter, and the array has n slots to record them, so the extra memory drops to O(1).

Try each candidate with a full scan

Correct, but does not finish on the largest tests

Intuition

Test the candidates 1, 2, 3, ... in order. For each, scan the whole array, and return the first candidate the scan does not find. By the bound, you never test past n+1.

When the array holds 1 to n, each candidate is found halfway through on average, so n = 10^4 costs about n²/2 = 5 × 10^7 comparisons.

Algorithm

Set candidate to 1.
Scan nums for an element equal to candidate, stopping at the first one.
If no element matches, return candidate.
Otherwise add 1 to candidate and scan again. You never go past n+1.

def firstMissingPositive(nums):
    n = len(nums)
    # n values cannot cover all of 1..n+1, so one of these candidates is missing
    for candidate in range(1, n + 2):
        found = False
        for num in nums:
            if num == candidate:
                found = True
                break
        if not found:
            return candidate

Mark the values 1 to n in a flag array

Intuition

Since the answer is at most n+1, skip any value below 1 or above n. A boolean array present of length n+1 records the rest, so a value like 10^9 is never stored. Return the first v from 1 to n whose flag is false, or n+1 if every flag is set.

In the first example n = 6: the flags for 1, 2, 3 and 5 get set, -2 and 9 are skipped, and the first unset flag is 4. Two linear passes give O(n) time, and the flags cost O(n) memory.

Algorithm

Create present, n+1 flags set to false.
For each value v in nums with 1 ≤ v ≤ n, set present[v] to true.
Return the first v from 1 to n whose flag is false.
If there is none, return n+1.

def firstMissingPositive(nums):
    n = len(nums)
    # present[v] says whether v is in nums; only 1..n can matter
    present = [False] * (n + 1)
    for num in nums:
        if 1 <= num <= n:
            present[num] = True
    for v in range(1, n + 1):
        if not present[v]:
            return v
    return n + 1

Place each value in its own slot

Intuition

Value v belongs at index v-1. With every value from 1 to n at home, the first index i that does not hold i+1 names the answer.

At each index, swap the value into its home while it is between 1 and n and the home does not already hold it. The value that comes back may need moving too. Checking the home, not i, stops duplicates: in [1, 1] the second 1 sees a 1 at index 0 and stays.

In the first example, index 0 sends the 5 home, then the 2 that comes back; later the 1 and the 3 go home, leaving [1, 2, 3, -2, 5, 9]: index 3 is the first wrong slot, so the answer is 4.

Each swap puts one value home for good, so the inner loops make at most n swaps in total: O(n) time, and O(1) memory except in R, which copies the vector it changes.

Algorithm

For each index i from 0 to n-1:
While 1 ≤ nums[i] ≤ n and nums[nums[i]-1] ≠ nums[i], swap nums[i] with nums[nums[i]-1].
After the placement pass, find the first index i where nums[i] ≠ i+1 and return i+1.
If every slot holds its own value, return n+1.

def firstMissingPositive(nums):
    n = len(nums)
    for i in range(n):
        # Keep swapping until slot i holds a value that has no slot or is already home
        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 names the answer
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1
    return n + 1

Pitfalls and edge cases

Stopping the swaps when nums[i] == i+1 instead of when the home already holds the value. With [1, 1], the two 1s swap forever.
Swapping with if instead of while. In the first example the 2 that comes back from index 4 never reaches index 1, and you return 2 instead of 4.
Writing nums[i] = nums[nums[i]-1] and then indexing with nums[i] again, which reads the home index after it changed. Save the home index first.
Skipping the range check, which sends 0, -2 or 10^9 to an index outside the array.
Returning n when every slot is right. For [4, 2, 1, 3] the answer is 5.

Frequently asked questions3

What is the time complexity of First Missing Positive?

The placement solution runs in O(n) time with O(1) extra space. The while loop sits inside a for loop, but each swap puts a value at its final index, so the whole run makes at most n swaps. The flag array version is O(n) time with O(n) memory, and scanning for each candidate is O(n²).

Why is the answer never larger than n+1?

The numbers 1 to n+1 are n+1 different values, and an array of length n holds at most n different values, so one of them is missing. The answer is n+1 exactly when the array holds every value from 1 to n.

Does the in-place solution change the input array?

Yes, it rearranges the values. If the caller needs the original order, copy the array first, which brings the extra memory back to O(n). Another in-place method replaces every value outside 1 to n with n+1, then marks v present by making nums[v-1] negative; it changes the array too.

def firstMissingPositive(nums):
    # Write code here

Test #1

Test #2

Test #3

Argument

nums = [5, -2, 1, 3, 2, 9]

Expected Output

First Missing Positive

Function

Constraints

Examples

Hints

Solution

Try each candidate with a full scan

Mark the values 1 to n in a flag array

Place each value in its own slot

Pitfalls and edge cases

Frequently asked questions3

Similar problems