First Missing Positive

Problem Id: 41 Difficulty: Hard Tag: Array


We could try to move every number to the right position and then check if there is anyone missed.

Notice that, even we used a while loop in the for loop, since each time we run the loop for once, one number would be put to the right position. And the total number is n, so it won't be executed for more than n times. So the overall time complexity is still O(n).


class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        for i in range(len(nums)):
            while 0 < nums[i] <= n and nums[i] != i + 1:
                j = nums[i] - 1
                if nums[j] == nums[i]:
                nums[j], nums[i] = nums[i], nums[j]

        for i in range(len(nums)):
            if nums[i] != i + 1:
                return i + 1

        return n + 1