First Missing Positive

Missing Number

Problem

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

Example:

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

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

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

Thought Process

• Notice how we can match each element to it's corresponding matching index in the array

• Since we only care about the first missing positive number, we do not care about numbers greater than n (length of the array), nor do we care about negatives or zeroes. So we will switch these to 1.

  • We set 0's to ones because we will use the 0th index as a place holder for any element equal to n (since there can't be an nth index)

• Iterate through the array and map the corresponding element to it's matching index in the array, switching the element at this index to a negative (if the element is less than n length). Else if the element is equal to the length, map it to the 0th index and turn this number negative.

• At the end, the index with a positive element will be our missing number in the array

Solution

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        hasOne = False
        n = len(nums)
        for i in range(len(nums)):
            if nums[i] == 1:
                hasOne = True
                
        if(hasOne == False):
            return 1
        
        for i in range(n):
            if nums[i]<= 0 or nums[i] > n:
                nums[i] = 1
        
        for i in range(n):
            #have to do abs cause to get the positive 
            #index if this element is already negative
            index = abs(nums[i]) 
            
            if index < n:
                nums[index] = abs(nums[index]) * -1
                
            else:
                nums[0] = abs(nums[0]) * -1
                      
        for i in range(1,n):
            if nums[i] > 0:
                return i
        if nums[0] > 0:
            return n
        return n+1

Key Facts

• We are mapping the current element to it's matching index in the array, and changing the element at the matching index to a negative.

• Our for loop starts at index 1 and not 0 ecause if index 0 is used to see if the length of our array is the first missing positive. If it is the first missing positive, we can't simply return index i since this will return 0. So that is why we have a seperate check for nums[0] > 0, and not checking this index in our for loop.

• The reason why this algorithm works is because we are controlling the range in which we are looking for the first missing positive number, which is between 1 to n (length of the array).

  • The reason why this is the range is because 1) We do not care about zero since it's not positive (same goes for negatives) 2) We do not care about numbers greater than n, because if numbers from 1 to n are present in the array then the next missing positive is n+1

Time Complexity

• Time: $O(n)$

• Space: $O(1)$