DSA First Missing Positive

The problem

The first missing positive is the smallest positive whole number that does not appear in a list. The list is unsorted. It may hold negatives, zero, duplicates and values far above its own length.

The answer always sits between 1 and n plus 1, where n is the length of the list. A list of four values cannot miss 1, 2, 3 and 4 and also 5 at once, and 5 is the largest possible answer.

cases = [
    ([3, 4, -1, 1], 2),
    ([1, 2, 0], 3),
    ([7, 8, 9, 11, 12], 1),
    ([1, 1, 2, 2], 3),
    ([1, 2, 3], 4),
]
for nums, expected in cases:
    print("nums", nums, "-> missing:", expected)

The last row holds every value from 1 to 3. Its answer is 4, one past the length. That row is the boundary case for the whole method.

Intuition: hunt for 1, then 2, then 3

The first idea checks candidates in order. Is 1 in the list? Is 2? The first candidate that fails the check is the answer.

Each check scans the list from the front. The idea is correct. Its cost is one full scan per candidate.

nums = [3, 4, -1, 1]
candidate = 1
while True:
    checks = 0
    found = False
    for value in nums:
        checks += 1
        if value == candidate:
            found = True
            break
    print("candidate", candidate, "found:", found, "comparisons:", checks)
    if not found:
        print("answer:", candidate)
        break
    candidate += 1

Candidate 1 costs four comparisons because it sits at the very end. Candidate 2 costs four more and fails. The scans repeat work that a single arrangement pass can do once.

Brute force: one scan per candidate, counted

The brute force is the intuition as a function. It scans for each candidate from 1 upward. It stops at the first absent candidate.

def brute(nums):
    checks = 0
    candidate = 1
    while True:
        found = False
        for value in nums:
            checks += 1
            if value == candidate:
                found = True
                break
        if not found:
            return candidate, checks
        candidate += 1

for nums in [[3, 4, -1, 1], [1, 2, 0], [7, 8, 9, 11, 12]]:
    answer, checks = brute(nums)
    print(nums, "-> missing:", answer, "comparisons:", checks)

A sorted copy or a set would also work, and both spend extra memory or a sorting pass. The placement method below spends neither. It rearranges the list itself.

The optimal solution: park each value in its home slot

The state is the list itself, rearranged. Value v belongs at index v minus 1, and swapping each misplaced value into its home slot puts every present value from 1 to n in place, after which the first wrong slot names the answer.

Values outside 1 to n have no home slot. They are left wherever they sit. A swap is only made when the home slot holds a different value, so duplicates cannot loop forever.

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

cases = [
    ([3, 4, -1, 1], 2),
    ([1, 2, 0], 3),
    ([7, 8, 9, 11, 12], 1),
    ([1, 1, 2, 2], 3),
    ([1, 2, 3], 4),
]
for nums, expected in cases:
    answer, swaps, placed = first_missing(list(nums))
    print(nums, "-> placed:", placed, "swaps:", swaps, "missing:", answer, "match:", answer == expected)

Every case matches. The large-values row needs no swaps at all, because none of its values has a home slot. Its first slot is already wrong, and the answer is 1.

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

The walk runs the placement loop on the first case. The list is printed after every swap. Three swaps park 3, 4 and 1.

nums = [3, 4, -1, 1]
n = len(nums)
print("start:", nums)
for i in range(n):
    while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
        j = nums[i] - 1
        nums[i], nums[j] = nums[j], nums[i]
        print("swap into index", j, "->", nums)
for i in range(n):
    if nums[i] != i + 1:
        print("first wrong slot: index", i, "holds", nums[i], "expected", i + 1)
        print("answer:", i + 1)
        break

The stray -1 ends at index 1. Index 1 expects the value 2. The scan reads the answer straight off that mismatch.

Complexity

Placement makes at most one swap per value, because each swap parks a value in its home slot for good. The placement pass and the final scan are each one walk, so the time is O(n).

No second list and no set is built, so the extra space is O(1). The brute force rescans per candidate, and its comparisons grow with the square of the length in the worst case.

def brute_checks(nums):
    checks = 0
    candidate = 1
    while True:
        found = False
        for value in nums:
            checks += 1
            if value == candidate:
                found = True
                break
        if not found:
            return checks
        candidate += 1

def placement_swaps(nums):
    nums = list(nums)
    n = len(nums)
    swaps = 0
    for i in range(n):
        while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
            j = nums[i] - 1
            nums[i], nums[j] = nums[j], nums[i]
            swaps += 1
    return swaps

for n in [4, 8, 16]:
    nums = list(range(n, 0, -1))
    print("n", n, "- brute comparisons:", brute_checks(nums), " placement swaps:", placement_swaps(nums))

The reversed lists hold every value from 1 to n, so the brute force scans for all of them and then for n plus 1. Its count passes 100 at n 16. The swap count stays under n.

Edge cases and pitfalls

An empty list misses 1. A list holding exactly 1 to n misses n plus 1. Duplicates park one copy at home and leave the spare in a wrong slot, where the scan finds it.

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

for nums in [[], [1, 2, 3], [2], [1], [1, 1, 2, 2], [-1, -2]]:
    answer, swaps, placed = first_missing(list(nums))
    print(nums, "-> placed:", placed, "missing:", answer)

The guard inside the swap loop is the pitfall guard. Without the check that the home slot holds a different value, two copies of one value would swap back and forth forever.