First Missing Positive in Python

The First Missing Positive problem is a common coding challenge where you need to find the smallest missing positive integer from an unsorted list of integers. This problem tests your ability to manipulate arrays and use optimal algorithms to solve problems efficiently.

Problem statement

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

Example

1nums = [1, 2, 0]
2# Output: 3

Explanation: The smallest missing positive integer in the array is 3.

How to solve

To solve the First Missing Positive problem efficiently, we can use an algorithm with O(n) time complexity and O(1) space complexity (excluding the input array). The idea is to place each number in its corresponding index position (i.e., 1 should be at index 0, 2 should be at index 1, and so on). After this arrangement, the first index that does not match its value will give the smallest missing positive integer.

Pseudo code

Here is the pseudo code to solve the First Missing Positive problem:

Iterate through the array.

For each number, place it in its correct index position.

Iterate through the array again to find the first incorrect position.

Return the missing positive integer.

Full code in Python

Here's the complete Python code to solve the First Missing Positive problem:

1def firstMissingPositive(nums):
2    n = len(nums)
3    
4    # Place each number in its correct position
5    for i in range(n):
6        while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
7            nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
8    
9    # Find the first missing positive
10    for i in range(n):
11        if nums[i] != i + 1:
12            return i + 1
13    
14    return n + 1
15
16# Example usage
17print(firstMissingPositive([1, 2, 0]))  # Output: 3
18print(firstMissingPositive([3, 4, -1, 1]))  # Output: 2
19print(firstMissingPositive([7, 8, 9, 11, 12]))  # Output: 1

Time complexity

The time complexity of this solution is O(n), where n is the number of elements in the array. This is because each element is placed in its correct position at most once.