Smallest Absent Positive
Problem
A ticket machine hands out the smallest positive ticket number that is not already taken. Given an unsorted list of whole numbers, which may include zero, negatives, duplicates and values far larger than the list, return the smallest positive whole number missing from it. Use O(n) time and only constant extra memory, rearranging the list itself if that helps.
Examples
Input: nums = [5, 3, -1, 1, 2]
Output: 4
Why: 1, 2 and 3 are all present, and 4 is notInput: nums = [2, 2, 90]
Output: 1
Why: 1 is missing, whatever else the list holdsInput: nums = []
Output: 1
Why: edge case, nothing is taken yetHints
0 / 3
A list of length n can hold at most the values 1 to n, so the answer is always somewhere from 1 to n + 1. Every value outside that range can be ignored.
If each value v from 1 to n sat at index v - 1, a single scan would reveal the first index whose value is wrong. That is exactly the arrangement cyclic sort builds.
For each index, keep swapping its value to its home index while the value lies from 1 to n and its home does not already hold the same value. Then scan for the first index i where the value is not i + 1 and return i + 1, or return n + 1 if every slot is correct.
Solution
With n slots, the missing positive is at most n + 1, so only the values 1 to n matter and each has a home index. Cyclic sort sends every such value home with swaps, and each swap settles one value for good, so the total number of swaps is at most n even though a while loop sits inside the for loop. Checking that the home does not already hold the same value stops duplicates from swapping forever. After that, the first slot holding the wrong value names the answer. Time is O(n), and space is O(1) beyond the input list.
def first_missing(nums):
n = len(nums)
for i in range(n):
# send nums[i] home while it belongs somewhere and home is not settled
while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
j = nums[i] - 1
nums[i], nums[j] = nums[j], nums[i]
for i in range(n):
if nums[i] != i + 1:
return i + 1 # the first slot without its own value
return n + 1 # 1..n are all present
print(first_missing([5, 3, -1, 1, 2])) # -> 4
print(first_missing([2, 2, 90])) # -> 1
print(first_missing([])) # -> 1Stuck on the idea rather than the code? Cyclic Sort covers it.