Python - O(n) time, O(1) space, float trick

  • 0

    The result will be between 1 and len(nums)+1 including, so we can use the indexes of the list. But there's no need to swap, sort or remove any elements. We can remember that number k appeared in nums by changing (k-1)th number to float.

    Runtime: 49 ms. If someone can make this idea run faster, I'd like to hear about it.

    class Solution(object):
        def firstMissingPositive(self, nums):
            :type nums: List[int]
            :rtype: int
            for num in nums:
                if num>0:
                    try: #we don't care about numbers bigger than len(nums)
                        nums[int(num)-1] *= 1.0
            for i in xrange(len(nums)):
                if type(nums[i]) != float:
                    return i+1
            #there were all the numbers between 1 and len(nums)
            return len(nums)+1

Log in to reply

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