Finding the First Missing Positive Integer in an Unsorted List
In many programming scenarios, one may wish to determine the smallest missing positive integer from an unsorted array. This task can be efficiently tackled using a combination of array indexing and in-place modifications.
Problem Statement
Given an unsorted list of integers, the goal is to find the smallest positive integer that is not present in the list.
Approach
1. In-place Hashing: The idea is to use the indices of the array itself to keep track of the presence of integers. Since the smallest missing integer will be between 1 and n + 1 (where n is the length of the list), we can ignore numbers greater than n and negative numbers.
2. Swapping Elements: By iterating through the array, we can place each number x in its corresponding index x-1 if 1 <= x <= n.
3. Final Pass: In a subsequent iteration, the first index that does not satisfy the condition array[i] == i + 1 gives us the smallest missing positive integer.
Implementation
Below is a Python function that implements the above logic.
def first_missing_positive(nums):
n = len(nums)
# Place each number in its right place (i.e., nums[i] = i + 1)
for i in range(n):
while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
# Swap nums[i] with nums[nums[i] - 1]
nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
# Find the first missing positive
for i in range(n):
if nums[i] != i + 1:
return i + 1
return n + 1 # all numbers are in the correct position
Explanation of the Code
- The function first_missing_positive takes a list of integers nums as its parameter.
- It first determines the length of the list, n.
- A loop is used to iterate through the array to position numbers in their respective indices. The condition checks if the number is within the valid range and if it is not already at the correct index.
- After rearranging, a second loop iterates through the modified list to find the first index where the number does not equal index + 1, which indicates the smallest missing positive integer.
- If all positions are filled correctly, the function returns n + 1, indicating that the smallest missing positive integer is n + 1.
Complexity Analysis
- Time Complexity: O(n) because each element is processed at most twice.
- Space Complexity: O(1) since the sorting is done in-place and no additional storage is required.
This function is a robust solution for efficiently finding the first missing positive integer in an unsorted list.