Python 42ms O(n) time O(1) space


  • 0

    Doing 3 passes:

    1. set all negatives to 0.
    2. mark each index if that number exists by multiplying the value at index by -1. If the value is 0 It's set to a negative value greater than the length of the array to indicate the value exists but wouldn't be considered as a missing value.
    3. loop through until the first 0 or negative value is found.
        def firstMissingPositive(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            if not nums: return 1
            flag = len(nums)+1
            for i in range(len(nums)):
                if nums[i] < 0: nums[i] = 0
            for i,v in enumerate(nums):
                if v == 0 or abs(v)-1 >= len(nums): continue
                ind = abs(v)-1
                if nums[ind] < 0: continue
                nums[ind] = -nums[ind] if nums[ind] else -flag
            for i,v in enumerate(nums):
                if v > -1: return i+1
            return flag
    

Log in to reply
 

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