LC 41, first missing positive

Given an unsorted array, find the smallest missing positive. Constrain: O(n) runtime and O(1) space

Brute Force

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

Bugs

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.

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax