💡 Problem Formulation: The problem is to identify the smallest positive integer that does not appear in a given sequence of numbers. For instance, given an input [3, 4, -1, 1], the desired output is 2, because it is the smallest positive integer missing from the list.
Method 1: Sorting and Linear Scan
This method involves sorting the array and then performing a linear scan to find the first missing positive. It is straightforward and works well for smaller lists. The complexity is dominated by the sorting algorithm, which in Python is O(n log n).
Here’s an example:
def first_missing_positive(nums):
nums.sort()
result = 1
for num in nums:
if num == result:
result += 1
return result
print(first_missing_positive([3, 4, -1, 1]))Output: 2
This function first sorts the input list. It initializes the result variable to 1, which is the smallest positive integer. The for loop iterates over the sorted numbers, and if a number equals the current result, the result is incremented. Finally, it returns the result, which represents the first missing positive.
Method 2: Hash Set
The hash set method creates a set from the input list and then checks for the first positive integer not present in the set. This approach has O(n) time complexity, as set operations in Python are generally O(1).
Here’s an example:
def first_missing_positive(nums):
num_set = set(nums)
result = 1
while result in num_set:
result += 1
return result
print(first_missing_positive([3, 4, -1, 1]))Output: 2
In this code, we create a set from the list to enable O(1) lookups. We then start with result set to 1 and iterate, increasing the result by 1 until we find a value not present in the set. We then return that missing positive integer.
Method 3: Cyclical Sort
Cyclical sort takes advantage of the fact that the first missing positive must be in the range [1, n+1], where n is the length of the list. We place each value in its corresponding index, disregarding negative numbers and numbers larger than n. This is an in-place algorithm with O(n) complexity.
Here’s an example:
def first_missing_positive(nums):
n = len(nums)
for i in range(n):
while 1 <= nums[i] <= n and nums[i] != nums[nums[i] - 1]:
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
print(first_missing_positive([3, 4, -1, 1]))Output: 2
This code moves each number to the index that matches its value, swapping as needed while iterating through the list. Once all numbers are moved or discarded, a second loop checks for the first index not containing its corresponding value, which will be our result. If all positions are correct, n+1 is the missing number.
Method 4: Optimized Space Usage
This method optimizes space by using the input list itself to store information. We mark the presence of numbers by negating the element at the index of the number we encounter. It works with O(n) time complexity and does not use extra space.
Here’s an example:
def first_missing_positive(nums):
n = len(nums)
for i in range(n):
if nums[i] n:
nums[i] = n + 1
for num in nums:
num = abs(num)
if 1 <= num 0:
return i + 1
return n + 1
print(first_missing_positive([3, 4, -1, 1]))Output: 2
The code snippet replaces all negative numbers and numbers greater than n with n+1. We then iterate through the array, using the value of each number to index into the array, negating the value at that index to indicate presence. Finally, we loop through to find the first positive value’s index, which gives us our result.
Bonus One-Liner Method 5: Pythonic Approach with Set
The bonus one-liner is a Pythonic way to solve the problem using a generator expression within a set to find the first number missing. It is a concise and straightforward method but may not be as efficient due to the use of extra space.
Here’s an example:
print(next(i for i in range(1, len(nums) + 2) if i not in set(nums)))
Output: 2
This one-liner first creates a range that extends one past the length of the list (to account for the potential missing n+1 case). Then it uses the next() function to find the first number in that range not present in a set constructed from the list. It’s simple but can use a lot of memory for large lists.
Summary/Discussion
- Method 1: Sorting and Linear Scan. Simple. The time complexity might be an issue for large lists due to sorting.
- Method 2: Hash Set. Quick and easy. Uses extra memory to create the set.
- Method 3: Cyclical Sort. Efficient. Can be difficult to understand and implement correctly for some.
- Method 4: Optimized Space Usage. Space-efficient in-place modifications. Mutates the input array, which might not be desirable.
- Method 5: Pythonic Approach with Set. Extremely concise. Uses extra space and might not be the best for performance.