Find the smallest missing positive in O(n) time and O(1) space: swap each value into its own seat, then the first wrong seat is the answer.
▼The problem
LeetCode 41 (Hard). Given an unsorted integer array nums, return the smallest positive integer that is not in nums, in O(n) time and O(1) extra space.
Examples (LeetCode's): [1,2,0] → 3, [3,4,-1,1] → 2 (walked through in scene 6) and [7,8,9,11,12] → 1.
The solution
def firstMissingPositive(nums):
n = len(nums)
for i in range(n):
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
return n + 1Transcript
First Missing Positive. Given an unsorted array of integers, return the smallest positive number that is missing. The catch: linear time, and constant extra space.
One, two, zero gives three. Three, four, minus one, one gives two. Seven, eight, nine, eleven, twelve: even one is missing, so one.
The easy ways cost too much. Sorting first is n log n. A hash set of every value is linear time, but n extra space.
The key: with n numbers, the answer is between one and n plus one, so the array itself can be the hash table. Think of a hotel with rooms one to n. Value v belongs in room v. Zero, negatives, and numbers bigger than n have no room, so they stay put.
In code: for each slot, while its number fits and its room doesn't already hold it, swap it home. Then scan. The first slot i that doesn't hold i plus one gives i plus one. Otherwise, n plus one.
Let's walk three, four, minus one, one. Three goes to room three, and minus one comes back. Four goes to room four, and one comes back. One goes to room one. Minus one stays. Scan: room one is right. Room two holds minus one. The answer is two.
Each swap sends a number home for good, so at most n swaps. Order n time, order one extra space. Flipping signs to mark seen values works too.
Skip what has no room, send each number home, then find the first wrong room. That's First Missing Positive.