First Missing Positive

Problem Id: 41 Difficulty: Hard Tag: Array


Intuition

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).

Solution


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]:
                    break
                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