Problem Statement in English

You are given an integer array nums. You should find the first missing positive integer.

The catch is that the solution should be in $O(n)$ time and $O(1)$ space.

Approach

The idea is to use the array itself to store the information about the presence of a number.

$0$ is not considered a positive number, and so can never be part of the answer. Hence we use 1 based indexing.

The next thing we need to do is eliminate all negative numbers. How do we do that? We’ll get back to this in a moment.

Now we need to be able to mark numbers as present when we encounter them. Since the answer can never be a negative number, we can mark the position that a number should ideally exist in a sorted set, by making it negative. Like:

[1, 5, 3, 4] –> [-1, 5, -3, -4]

But what about the numbers that are out of bounds? We can ignore them, as they are not part of the answer.

Now circling back to the question of how to eliminate negative numbers. The simplest thing is to exploit the fact that we don’t attempt to mark numbers that are out of bounds. So we can use a default value to mark all negative numbers.

In my code, the default value that I’m using is the $len(nums) + 1$.

And we are done!

Solution in Python


class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        l = len(nums)
        default = l+1

        for i in range(l):
            if nums[i] <= 0:
                nums[i] = default
        
        for i in range(l):
            val = abs(nums[i])-1

            if val < l:
                print(val)
                nums[val] = -1 * abs(nums[val])

        for i in range(l):
            if nums[i] > 0:
                return i+1

        return l+1

Complexity

  • Time: $O(n)$
    Since we iterate over the array thrice, the time complexity is $O(n)$

  • Space: $O(1)$
    Since we use just a few variables, the space complexity is $O(1)$

Mistakes I Made

I had to look this one up :(

And we are done.