Given an unsorted integer array nums, return the smallest positive integer (1, 2, 3, ...) that does not appear in it. Your algorithm must run in O(n) time and use only O(1) extra space.
- 1 <= nums.length <= 10^5
- -2^31 <= nums[i] <= 2^31 - 1
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Sorting is O(n log n) and a hash set is O(n) space, both against the rules. The key fact: an array of n numbers can contain at most all of 1..n, so the answer lies in 1..n + 1. That lets us use the indices of the array as our "set": cyclic sort places each value v (when 1 <= v <= n) at index v - 1 by repeated swaps. Each swap puts one value in its final home, so there are at most n swaps in total.
Algorithm
- For each index
i, while1 <= nums[i] <= nandnums[nums[i] - 1] != nums[i], swapnums[i]into indexnums[i] - 1. - Scan again: the first
iwherenums[i] != i + 1meansi + 1is missing. - If every position is correct, return
n + 1.
O(n)Space: O(1)nums[nums[i] - 1] != nums[i], not nums[i] != i + 1, or duplicates like [1,1] cause an infinite loop.class Solution: def firstMissingPositive(self, nums: List[int]) -> int: n = len(nums) for i in range(n): # move nums[i] to its home index nums[i] - 1 while that is possible and useful while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]: home = nums[i] - 1 nums[home], nums[i] = nums[i], nums[home] for i in range(n): if nums[i] != i + 1: return i + 1 return n + 1