Python solution with 2 linear passes


  • 0
    B

    In the first pass, check every element, if it is greater than zero then swap it such that its position in the array reflects it value. (arr[x + 1] == x ) . For eg. If 1 is present, it should be placed in 0th postion.For values greater than array size, skip them.

    In the second pass, check the elements whose value does not reflect their positions. (i.e arr[x + 1] != x) and return it. In case all elements are correctly placed, return the length of the array + 1

    class Solution(object):
        def firstMissingPositive(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            
            if nums is None or len(nums) == 0:
                return 1
            
            for x in xrange(len(nums)):
                while True:
                    if nums[x] <= 0 or nums[x] == (x + 1):
                        break
                    else:
                        index = nums[x] - 1
                        if index >= len(nums) or nums[index] == nums[x]:
                            break
                        
                        tmp = nums[index]
                        nums[index] = nums[x]
                        nums[x] = tmp
                        
            for x in xrange(len(nums)):
                if nums[x] != x + 1:
                    return x + 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.