41. First Missing Positive

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

You must implement an algorithm that runs in O(n) time and uses constant extra space.

 

Example 1:

Input: nums = [1,2,0]
Output: 3
Explanation: The numbers in the range [1,2] are all in the array.

Example 2:

Input: nums = [3,4,-1,1]
Output: 2
Explanation: 1 is in the array but 2 is missing.

Example 3:

Input: nums = [7,8,9,11,12]
Output: 1
Explanation: The smallest positive integer 1 is missing.

 

Constraints:

  • 1 <= nums.length <= 105
  • -231 <= nums[i] <= 231 - 1


The problem can be solved in O(n) time and constant space by using the input array itself as a hash map. We can iterate over the array and use the value at each index as the key to mark that key as seen. Then, we can iterate over the array again and return the first index that has not been marked as seen. This will give us the smallest missing positive integer.

Here is the python code that implements this solution:

def firstMissingPositive(nums):
    # Mark each element in the array as seen.
    for i in range(len(nums)):
        index = abs(nums[i]) - 1
        if 0 <= index < len(nums):
            nums[index] = -abs(nums[index])

    # Return the first index that has not been marked as seen.
    for i in range(len(nums)):
        if nums[i] > 0:
            return i + 1

    # If all numbers in the array are marked as seen,
    # then the missing number is the length of the array + 1.
    return len(nums) + 1

Here is how the algorithm works for the input [1, 2, 0]:

  1. We iterate over the array and mark each element as seen by negating the value at the corresponding index. Since 1 is at index 0, we negate nums[0] to get -1. Since 2 is at index 1, we negate nums[1] to get -2. Since 0 is at index 2, we do not negate nums[2] because the index is out of range. After the first iteration, the array becomes [-1, -2, 0].

  2. We iterate over the array again and return the first index that has not been marked as seen. Since nums[0] is negative, we skip it. Since nums[1] is negative, we skip it. Since nums[2] is positive, we return 2 + 1 = 3.

The time complexity of this algorithm is O(n) because we iterate over the array twice, and the space complexity is constant because we only use a constant number of variables.

Hope it helps!