class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        """
        This function finds the first missing positive integer in an unsorted array `nums`.

        Approach:
        1. Segregate positive numbers from negatives and zeros, as they are irrelevant.
        2. Use the array itself to track the presence of elements using in-place hashing.
        3. Check for the first missing positive integer.

        Arguments:
        nums -- list[int]: An unsorted list of integers

        Returns:
        int: The first missing positive integer
        """

        # Helper function to swap elements
        def swap(i, j):
            nums[i], nums[j] = nums[j], nums[i]

        n = len(nums)

        # Step 1: Segregate positive numbers
        for i in range(n):
            # Swap elements to their correct positions if possible
            while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
                swap(i, nums[i] - 1)

        # Step 2: Find the first position where its index doesn't match the value
        for i in range(n):
            if nums[i] != i + 1:
                return i + 1

        # Step 3: If all positions are correct, the missing number is n + 1
        return n + 1