# First Missing Positive in Python

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