Missing Positive [Solution]

This problem assesses the your ability to manipulate arrays, find patterns in numbers, and implement an algorithm with specific constraints.

Below is a Python implementation of the first_missing_positive function to find the smallest missing positive integer in an unsorted array:

from typing import List

def first_missing_positive(nums: List[int]) -> int:
    n = len(nums)

    # Rearrange the array to put each positive integer at its correct position
    for i in range(n):
        while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
            nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]

    # Find the smallest missing positive integer
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1

    # If all integers are in their correct positions, the missing positive is n + 1
    return n + 1

# Example usage:
nums = [3, 4, -1, 1]
result = first_missing_positive(nums)
print(result)  # Output: 2

nums = [1, 2, 0]
result = first_missing_positive(nums)
print(result)  # Output: 3

This solution follows the concept of cyclic sort to rearrange the array and then iterates through it to find the smallest missing positive integer. The time complexity is O(n), and the space complexity is O(1).