First Missing Positive - Python Solution

1. Introduction

"First Missing Positive" is an algorithmic challenge that focuses on finding the smallest missing positive integer in an unsorted array. This problem is significant for its constraints on time and space complexity, requiring a solution with O(n) time and O(1) auxiliary space. It's a test of one's ability to perform in-place array manipulations efficiently.

Problem

Given an unsorted integer array nums, the objective is to find and return the smallest missing positive integer. The solution must run in O(n) time and use only O(1) auxiliary space.

2. Solution Steps

1. Iterate over the array and for each element, place it in its correct position if possible. For example, if the element is x, place it at index x-1.

2. Swap elements to their correct positions as long as they are in the range of 1 to n (array length) and are not already in the correct place.

3. After rearranging, iterate through the array again.

4. The first position where its index does not match the value gives the first missing positive integer.

5. If all positions are correct, the first missing positive is n+1.

3. Code Program

def firstMissingPositive(nums):
    n = len(nums)
    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]

    for i in range(n):
        if nums[i] != i + 1:
            return i + 1
    return n + 1

# Example Usage
print(firstMissingPositive([1,2,0]))  # Output: 3
print(firstMissingPositive([3,4,-1,1]))  # Output: 2
print(firstMissingPositive([7,8,9,11,12]))  # Output: 1

Output:

3
2
1

Explanation:

1. In-place Rearrangement: The array is rearranged in-place to place each number at its correct index.

2. Correct Positioning: Each element is moved to the index corresponding to its value.

3. First Missing Positive: Iterates through the array to find the first index where the value does not match the index.

4. Edge Case Handling: Considers the case where all positives are present and the missing positive is n+1.

5. Time Complexity: Achieves O(n) time complexity by ensuring each element is swapped at most once.

6. Space Complexity: Maintains O(1) auxiliary space, as no additional storage is used.

7. Practical Use: Demonstrates efficient array manipulation and in-place algorithms.