First Missing Positive

Naive Solution

The most straightforward approach is to iterate from 1 and check for the presence of each positive integer in the array. This continues until we find the first missing positive integer.

Code

def first_missing_positive_naive(nums):
    n = len(nums)
    for i in range(1, n + 2):
        if i not in nums:
            return i

Time Complexity

O(n*m), where n is the range we search in and m is the length of the array. In the worst case scenario, we might iterate through a range almost as large as the array itself for each check.

Space Complexity

O(1), because no extra space scales with the input size is used.

Optimal Solution

The optimal solution uses the input array itself as a hash table. The basic idea is that if k is present in the array, we try to place it at index k-1. Then we iterate through the array, and the first index i where nums[i] != i + 1 is the index where the missing positive number is i + 1.

Algorithm

1. Check if 1 is present in the array. If not, you're done and 1 is the answer.
2. Replace negative numbers, zeros, and numbers larger than n by 1.
3. Walk along the array. Change the sign of a-th element if you meet number a. Be careful with duplicates: do sign change only once.
4. Walk again along the array. Return the index of the first positive element.
5. If nums[0] > 0, return n + 1. If during the previous steps you didn't find the positive element in nums, that means that the answer is n + 1.
6. If nums[0] < 0, return n + 2. This implies all numbers from 1 to n were present.

Code

def first_missing_positive(nums):
    n = len(nums)

    # Base case.
    if 1 not in nums:
        return 1

    # Replace negative numbers, zeros, and numbers larger than n by 1.
    # After this conversion, nums will contain only positive numbers.
    for i in range(n):
        if nums[i] <= 0 or nums[i] > n:
            nums[i] = 1

    # Use the index as a hash key and the sign of the number as a presence detector.
    # For example, if nums[1] is negative, that means that the number `1`
    # is present in the array.
    # If nums[2] is positive, the number 2 is missing.
    for i in range(n):
        a = abs(nums[i])
        # If you meet number a in the array, change the sign of the a-th element.
        # Be careful with duplicates: do sign change only once.
        if a == n:
            nums[0] = - abs(nums[0])
        else:
            nums[a] = - abs(nums[a])

    # Now the index of the first positive number is equal to the first missing positive.
    for i in range(1, n):
        if nums[i] > 0:
            return i

    if nums[0] > 0:
        return n

    return n + 1

Time Complexity

O(n), because each step iterates through the array at most a constant number of times.

Space Complexity

O(1), because the algorithm uses constant extra space.

Edge Cases

• Empty array: While the constraints state the array will not be empty, it's good practice to consider. The algorithm handles this implicitly by returning 1.
• Array with only negative numbers: The algorithm correctly identifies 1 as the missing positive integer.
• Array with all positive numbers from 1 to n: The algorithm returns n+1.
• Array with duplicates: The sign change is handled such that duplicates do not cause incorrect results.