First Missing Positive

Patrick Leaton
Published: June 3, 2021, 6:46 a.m.
Problem Description

Given an unsorted integer array nums, find the smallest missing positive integer.

Follow up: Could you implement an algorithm that runs in O(n) time and uses constant extra space.?

 

Example 1:

Input: nums = [1,2,0]
Output: 3

Example 2:

Input: nums = [3,4,-1,1]
Output: 2

Example 3:

Input: nums = [7,8,9,11,12]
Output: 1

 

Constraints:

  • 0 <= nums.length <= 300
  • -2^31 <= nums[i] <= 2^31 - 1

 

The description was taken from https://leetcode.com/problems/first-missing-positive/.

Problem Solution

#O(N) Time, O(1) Space
class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        if 1 not in nums:
            return 1
 
        N = len(nums)
        for i in range(N):
            if nums[i] <= 0 or nums[i] > N:
                nums[i] = 1
   
        for i in range(0, N):
            abs_num = abs(nums[i])
            if abs_num == N:
                nums[0] = - abs(N)
            else:
                nums[abs_num] = - abs(nums[abs_num])
           
        for i in range(1,N):
            if nums[i] > 0:
                return i
       
        if nums[0] > 0:
            return N
       
        return N + 1

Problem Explanation

The first approach we'd probably consider is to sort the input array and increment a pointer then return which number wasn't increased by one.  That would be O(N(Log N)) time.

It may not be obvious, but the first missing positive would fall within the range of one to the length of the input array plus one.

Try to picture the array as a nearly complete collection of comic books.  If we had issue number one through six, issue seven hundred, and issue twenty-six, then we would be missing a bunch of issues between six and twenty-six, and between twenty-six and seven hundred.  Somebody might look at our collection and think "why didn't you just buy issue number seven next!?".

If we wanted to have a consecutive series and not miss gaps in the story, we would need issue numbers one through eight for a collection of eight comic books.  If our issues don't match up to the number of comic books we have, then we skipped issues and are probably missing a lot of action.

With that being said, we can use each index from one to the length of the array as a mapping to which number is present.  We will set the element at the index directly correlated to each iteration from one to N as negative, and when we traverse the list once more we will see which number is still positive.  That will be the first number we missed and will be our answer.

We will first start off by checking our base case of if one is missing from the array.

We want to do this first because one is the number that we are going to change the negative numbers and the numbers greater than the length of the array to.

        if 1 not in nums:
            return 1

 

Next, we will change any negative numbers and any numbers greater than the length of the array to one.

The reason we need to change them for example is if we had the number five hundred, and we wanted to change the element at index five hundred to negative, we would get an index out of bounds error.  We already know that one is in the array because we just checked earlier, so it is a safe index to keep editing for each invalid number.

        N = len(nums)
        for i in range(N):
            if nums[i] <= 0 or nums[i] > N:
                nums[i] = 1

 

Next, we will traverse the values of the input array.  Each value we will temporarily keep as an absolute value, because it may have been changed to negative previously.

        for i in range(0, N):
            abs_num = abs(nums[i])

 

If the current absolute number is equal to the length of the array, then we will set the number to negative and keep it at index zero.  We do this because arrays start at index zero and we are wanting to make it easier for us to keep track of each positive number from one to N-1 by being able to map one to one, two to two, etc.

            if abs_num == N:
                nums[0] = - abs(N)

 

Otherwise, we are going to set the element at the index of the absolute number to negative if it isn't already.

            else:
                nums[abs_num] = - abs(nums[abs_num])

 

Now we will traverse the list and see which element is still positive.  That will show us which number didn't come up when we were plugging values from the input array as indices.

If we find a positive number, we will return the index since that will be the first missing positive.

        for i in range(1,N):
            if nums[i] > 0:
                return i

 

If index zero is positive, then that means the length of the array is the first missing number because that is the index we were keeping N.

        if nums[0] > 0:
            return N

 

If nothing else, then the first missing positive is N+1 because we have a complete series and the next number would come after the series ends.

In other words, we already have the comic issue numbers one through eight and we are just waiting on issue number nine to come out next month.

        return N + 1

 

Additional Notes

If the problem says or indicates that values one through N should be present, consider using the indices of the array as a mapping to the seen values.

Similar questions that utilize this algorithm include:

https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array

https://leetcode.com/problems/find-all-duplicates-in-an-array