First Missing Positive

Given an unsorted integer array nums. Return the smallest positive integer that is not present in nums.

You must implement an algorithm that runs in O(n) time and uses O(1) auxiliary space.

Example 1:

Input: nums = [1,2,0]
Output: 3
Explanation: The numbers in the range [1,2] are all in the array.

Example 2:

Input: nums = [3,4,-1,1]
Output: 2
Explanation: 1 is in the array but 2 is missing.

Example 3:

Input: nums = [7,8,9,11,12]
Output: 1
Explanation: The smallest positive integer 1 is missing.

## Finding the Smallest Missing Positive Integer

This problem requires finding the smallest positive integer that is not present in an unsorted array of integers. The solution must operate in O(n) time and O(1) space.

### 1. Naive Approach (Brute Force)

The simplest approach is to iterate through positive integers starting from 1 and check for the presence of each integer in the array.  This approach has a time complexity of O(n*m) where n is the length of the array and m is the missing positive integer.

```python
def first_missing_positive_naive(nums):
    i = 1
    while True:
        if i not in nums:
            return i
        i += 1

2. Optimal Approach (In-place Hashing)

The optimal solution uses the input array itself as a hash table. The main idea is to rearrange the array such that nums[i] = i + 1. This can be done by swapping elements.

Here’s how it works:

1. Check for 1: If 1 is not present in the array, then 1 is the answer.
2. Replace Non-Positive and Out-of-Range Numbers: Replace negative numbers, zeros, and numbers larger than n with 1s.
3. In-place Hashing:
   • Iterate through the array.
   • For each number a, if abs(a) is within the range 1 to n, change the sign of the abs(a)-th element. Be careful with duplicate numbers: do sign change only once.
   • Use index 0 to save information about the presence of number n since index n is not available.
4. Find the First Positive Index: The index of the first positive number will be the first missing positive.
5. Handle the Case of all Negatives: If nums[i] are all negative, that means the answer is n + 1.

def first_missing_positive(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 the 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

3. Big(O) Time Complexity Analysis

The algorithm iterates through the array a fixed number of times (at most three times). Therefore, the time complexity is O(n).

4. Big(O) Space Complexity Analysis

The algorithm uses O(1) auxiliary space as it modifies the array in-place without using any additional data structures that scale with the input size.

5. Edge Cases and Handling

• Empty Array: If the array is empty, the function should return 1.
• Array with no positive integers: The function correctly handles this case by replacing non-positive integers with 1 and proceeding with the algorithm.
• Array with all positive integers from 1 to n: In this case, the function correctly returns n + 1.
• Array with duplicates: The in-place hashing handles duplicates by only changing the sign of an element once.

Example Walkthrough

Consider the input nums = [3, 4, -1, 1].

1. The array contains 1.
2. The array becomes [3, 4, 1, 1] after replacing -1 with 1.
3. Iterate through the array:
   • nums[0] = 3. nums[3] becomes negative: [3, 4, 1, -1]
   • nums[1] = 4. nums[4] is out of bounds, so ignore.
   • nums[2] = 1. nums[1] becomes negative: [3, -4, 1, -1]
   • nums[3] = -1.
4. The first positive element is nums[2] = 1. Therefore, the index 2 is the missing positive. Since we are looking for index+1 we return 2.