8-line Python solution, beats 79%

  • 0

    O(1) space can usually be done by mutating input list.
    The idea is try moving elements within the array such that number n is at index n-1. Then loop from 0->len(input)-1, if input[i] is None then i + 1 is missing. Otherwise return len(input) + 1
    Few points to note:

    • if n-1 is out of array boundary, we can't find a new index to move to, just skip.
    • If n is already in its correct position n - 1, do nothing.
        def firstMissingPositive(self, nums):
            :type nums: List[int]
            :rtype: int
            for i in range(len(nums)):
                tmp, nums[i] = nums[i], None
                while tmp is not None and 0 <= tmp-1 < len(nums) and tmp != nums[tmp-1]:
                    nums[tmp-1], tmp = tmp, nums[tmp-1]
            for i in range(len(nums)):
                if nums[i] is None:
                    return i+1
            return len(nums) + 1

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.