Naive Solution

The brute force approach involves iterating through positive integers starting from 1 and checking if each integer is present in the input array nums. The first positive integer not found in nums is the answer.

Algorithm

1. Start with i = 1.
2. Check if i exists in nums. If not, return i.
3. Increment i and repeat step 2.

Code

def firstMissingPositive_naive(nums):
    i = 1
    while True:
        if i not in nums:
            return i
        i += 1

Time Complexity

O(n*m), where n is the length of the array and m is the missing positive integer. In the worst case, m could be large, leading to a potentially high time complexity.

Space Complexity

O(1), as it uses constant extra space.

Optimal Solution

The optimal solution leverages the fact that we are looking for a positive integer in the range [1, n+1], where n is the length of the input array. We can use the input array itself as a hash table to mark the presence of numbers in the range [1, n]. The basic idea is to rearrange the array such that nums[i] = i + 1. If this is not possible, we return the index where nums[i] != i + 1.

Algorithm

1. Check for edge cases such as an empty array, return 1 in this instance.
2. Iterate through the array. If nums[i] is in the range [1, n] and nums[i] != nums[nums[i] - 1], swap nums[i] with nums[nums[i] - 1]. This places each number at its correct index (i.e., 1 at index 0, 2 at index 1, etc.).
3. After rearranging, iterate through the array. The first index i where nums[i] != i + 1 indicates that i + 1 is the smallest missing positive integer.
4. If the array contains all numbers from 1 to n, then the smallest missing positive integer is n + 1.

Code

def firstMissingPositive(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 index as a hash key and number sign 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 it 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), as it iterates through the array a few times.

Space Complexity

O(1), as it uses constant extra space.

Edge Cases

• Empty array: [] should return 1.
• Array containing only negative numbers: [-1, -2] should return 1.
• Array containing 1, but missing 2: [1] should return 2.
• Array containing all positive numbers from 1 to n: [1, 2, 3] should return n + 1.
• Array with duplicates and out-of-range numbers: [2, 2, -1, 10, 1] should return 3.
• Array with large positive integers [7,8,9,11,12] should return 1