Finding the Smallest Missing Positive Integer in a List
When dealing with arrays of integers, one common problem is identifying the smallest missing positive integer. This is particularly useful in various algorithms and data handling scenarios. Below is a Python function that efficiently determines this value.
Function Implementation
def smallest_missing_positive(nums):
# Initialize the size of the input list
n = len(nums)
# Step 1: Replace negative numbers and zeros with n+1
for i in range(n):
if nums[i] <= 0:
nums[i] = n + 1
# Step 2: Use the index to mark presence of numbers
for i in range(n):
num = abs(nums[i])
if 1 <= num <= n:
nums[num - 1] = -abs(nums[num - 1]) # Mark as negative
# Step 3: Determine the first missing positive
for i in range(n):
if nums[i] > 0:
return i + 1
return n + 1 # If all numbers from 1 to n are present
# Example Usage
if name == "main":
input_nums = [3, 4, -1, 1]
result = smallest_missing_positive(input_nums)
print(f"The smallest missing positive integer is: {result}")
Explanation of the Solution
1. Input Processing: The function starts by determining the size of the input list, n. It then iterates through the list, replacing all negative numbers and zero with n + 1. This value is a placeholder since it will not affect the outcome.
2. Marking Presence: In the second loop, the function marks the presence of each positive integer that lies within the range of 1 to n. If a number is found within this range, it will convert the number at the corresponding index (using num - 1) to negative. This negative marking indicates that the integer num exists in the array.
3. Finding the Missing Integer: The final loop checks each index of the modified array. The first index i where the value remains positive indicates that the missing integer is i + 1. If all indices have been marked negative, it means that all integers from 1 to n are present in the original list, and thus the smallest missing positive integer is n + 1.
Performance
This algorithm operates in linear time, O(n), and uses O(1) additional space since it modifies the input list in place. This efficiency makes it suitable for large datasets.
Overall, this function provides an effective solution to efficiently find the smallest missing positive integer within a given list of integers.