LC-0041 Hard LeetCode

41. First Missing Positive

Read the full problem statement on LeetCode.

Difficulty: hard Acceptance: 41% Topics: Array, Hash Table

Reading material

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(1)

class Solution(object):
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        for i in xrange(len(nums)):
            while 1 <= nums[i] <= len(nums) and nums[nums[i]-1] != nums[i]:
                nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]
        return next(((i+1) for i, x in enumerate(nums) if x != i+1), len(nums)+1)

Solution from kamyu104/LeetCode-Solutions · MIT