Same as LostSummer233 with more comments, Python, beats 87%, O(n) time, O(1) space


  • 0
    M

    Idea:
    The first missing positive number should >= 1 and <=len(nums).
    '''

        minvalue = 1
        maxvalue = len(nums)
    

    '''
    Using O(n) time and O(n) space, one could build an extra array containing booleans.

    1. Scan through the array to mark each number as exist or missing.
    2. Find the first missing positive number.

    Based on this idea, then we need to improve the code so that it uses O(1) extra space.
    A straight thinking is to use the array itself and modify the value in-place.

    1. If the nums[i] is in place (e. g. nums[0] == 1), go to next;
    2. If the value is not in place, swap it so that it is in place;
    3. if the value is out of boundary (too small, too large) or duplicated, discard the value, and the first missing positive number should now between 1 and maxvalue -1

    '''

    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        
        i, end = 0, len(nums)
        
        while i < end:
            j = nums[i]-1 # nums[i] should go to jth index
            if i == j: # nums[i] is in place
                i += 1
            # in case:
                # the value is smaller than 1;
                # the value is larger than largest possible
                # the value is duplicated
            elif nums[i] < 1 or nums[i] > end or nums[i] == nums[j]:
                end -= 1 # the largest possible -1
                nums[i] = nums[end] # discard the value and get new one from the end
            else:
                # swap the value, so nums[j] is in place
                nums[i], nums[j] = nums[j], nums[i]
        return i+1 # return the missing value, not the index
    

    '''


Log in to reply
 

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