Given an unsorted array, find the smallest missing positive. Constrain: O(n) runtime and O(1) space
Just sort the array, and then iterate through from beginning till end. Return the first element that has A[i] != i + 1.
Take away from Brute force method
It takes too long. But to find the smallest positive requires a sense of “order”. So we need to sort it but in O(n) time. We might need to use non comparison sort.
Counting sort variant
Counting sort is a non-comparison sort that sort lists of positive integer in O(n) time with O(n) extra space.
Counting will create an aux array of size size(A). This aux array will be used to see if an positive number exist. We init the array with all -1. We iterate through array A and put A[i] into aux[A[i] – 1]. After iteration, aux tells us weather positive integer i exists by checking aux[i – 1] != -1.
The size of the aux array is size(A). Even if we fill A with consecutive positive integer, the smallest missing positive will be size(A) + 1. Since we only care about the smallest missing positive size(A) is enough.
def firstMissingPositive(self, nums): """ :type nums: List[int] :rtype: int """ aux = [-1] * len(nums) for i in range(len(nums)): if nums[i] <= len(nums) and nums[i] > 0: aux[nums[i] - 1] = nums[i] for i in range(len(nums)): if aux[i] != i + 1: return i + 1 return (len(nums) + 1)
Use constant space
But we can’t use that much space. But we can use the given array as a array that keeps track of what number we have seen.
If 0 < A[i] < len(A), then A[i] should be in A[A[i] – 1]. If not, then we need to put A[i] in A[A[i] – 1].
Simply putting A[i] into A[A[i] – 1] would erase what was in A[A[i] – 1]. But we can just swap A[i] with A[A[i] – 1] to preserve what was in A[i]. Now what’s now in A[i] is out of place again, if the new A[i] is 0 < A[i] <= len(A) and A[i] != A[A[i] – 1], then we swap it again with A[A[i] – 1]. The swapping continues till either A[i] < 0 or A[i] > len(A).
def firstMissingPositive(self, nums): """ :type nums: List[int] :rtype: int """ for i in range(len(nums)): while 0 < nums[i] <= len(nums) and nums[i] != nums[nums[i] - 1]: temp = nums[i] nums[i] = nums[nums[i] - 1] nums[temp - 1] = temp for i in range(len(nums)): if nums[i] != i + 1: return i + 1 return len(nums) + 1
Swapping that uses array’s element as indices
In the last implementation, I orginally have
temp = nums[i] nums[i] = nums[nums[i] - 1] nums[nums[i] - 1] = temp
This piece of code was intended to swap two element. But the last line use nums[i], which was recently updated. Be careful when swapping things in array that uses array element as indices.
What if we want to find the largest missing positive?
Mirror negative to positive.