Cyclic sort
If nums only had positive numbers, we could cyclic sort it to match the sequence of positive integers and the first mismatch would have been the first missing positive number.
To reduce the original problem to the above, simpler, all-positive case, we first sort around pivot 1. From the pivot index onwards, all numbers are now positive.
Time: 
class Solution:
def sort_around_pivot(self, nums: List[int], pivot: int) -> int:
n = len(nums)
i, j, k = -1, 0, n
while j < k:
if nums[j] == pivot:
j += 1
continue
if nums[j] < pivot:
i += 1
nums[i], nums[j] = nums[j], nums[i]
j += 1
else:
k -= 1
nums[j], nums[k] = nums[k], nums[j]
pivot_index = i + 1
return pivot_index if pivot_index < n else -1
def cyclic_sort(self, nums: List[int], begin: int, end: int, offset: int) -> None:
for i in range(begin, end):
while (
nums[i] != i - begin + offset # mismatch
and (j := begin + nums[i] - offset) < end # value too big
and nums[i] != nums[j] # skip duplicate
):
nums[i], nums[j] = nums[j], nums[i]
def find_first_mismatch(self, nums: List[int], begin: int, end: int, offset: int) -> Tuple[int, int]:
for i in range(begin, end):
if ( expected := i-begin+offset ) != nums[i]:
return expected, nums[i]
return end-begin+offset, None
def firstMissingPositive(self, nums: List[int]) -> int:
pivot_index = self.sort_around_pivot(nums, 1)
if pivot_index < 0:
return 1
begin, end, offset = pivot_index, len(nums), 1
self.cyclic_sort(nums, begin, end, offset)
missing, _ = self.find_first_mismatch(nums, begin, end, offset)
return missing
unreasonably effective 
Leave a comment