Leetcode 41 Solution

Leetcode Question Link

https://leetcode.com/problems/first-missing-positive

Thinking Process

Solving the problem with O(N) space is easy. If we are asked to use O(1), the idea is basically to use the existing array to store information to infer if an element exists. One of the ways to do that is to place i onto the (i - 1)th position of the array.

Once we are done, we go through the array one more time

• If we find an element nums[j] != j + 1, j + 1 is the first missing positive number.
• If we cannot find anything like that, len(nums) + 1 is the result.

Time & Space Complexity

Assuming N is the size of the array,

• Time complexity: O(N)
• Space complexity: O(1)

Solution

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        for i, num in enumerate(nums):
            curr = num
            while 1 <= curr <= len(nums) and nums[curr - 1] != curr:
                tmp = nums[curr - 1]
                nums[curr - 1] = curr
                curr = tmp

        for i, num in enumerate(nums):
            if num != i + 1:
                return i + 1

        return len(nums) + 1