Given an unsorted integer array, find the smallest missing positive integer.

Function Signature:

from typing import List

def first_missing_positive(nums: List[int]) -> int:
    """
    Find the smallest missing positive integer in the given array.

    Parameters:
    - nums: List of integers.

    Returns:
    - int: The smallest missing positive integer.
    """
    # Your code here

Example:

# Input: [0]
# Ooutput: 1

# Input: [1, 2, 0]
# Output: 3

# Input: [3, -2, 4, 2]
# Output: 1

# Input: [3, 4, -1, 1]
# Output: 2

Note:

  • Your algorithm should run in O(n) time and use constant extra space.

Instructions:

  • Write the first_missing_positive function to solve the problem.
  • Implement your solution in Python.
  • Provide clear comments in your code.
  • Discuss the time and space complexity of your solution.

As always, we’ll share our solution to this problem tomorrow. Stay tuned 😊