Leetcode 41. First Missing Positive

Problem

Leetcode 41 - First Missing Positive

Example:

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

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

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

Approach

If we were to have an extra space, then we could use a HashSet to determine the first missing positive number. However, we’re not allowed any extra space we have to manipulate the array that is given.

We can run a while loop to reposition the element into according position/index. Meaning that if our element was 3, then we should place that element into index 2 (Since array counting starts at 0).

Since array’s element can have non positive number and a number that is bigger than its array size, we can simply ignore this if it happens.

Then we swap the place of element and element that is on that index if they’re different. Once swapping is all done, then we can run another for loop to check the missing first positive number.

To summarize the step is:

1. Running while loop (can’t be in for loop since when we swap, we need to check if swapped element is in place)
2. If that element is non positive or number that is bigger than length of nums we continue (increment the i value)
3. If the element is different (nums[i] != nums[index] where $index = nums[i]-1$)
   1. We swap the position of these elements
4. Else
   1. We continue (increment the i value)
5. Once while loop is done, we can start the for loop to find the missing positive number

Visualization of the Approach:

nums = [3, 4, -1, 1]
i = 0
n = 4

nums[i] = 3
index = 3-1 = 2
Since nums[index] != nums[i], we swap elements
nums = [-1, 4, 3, 1]

i = 0
nums[i] = -1
Since nums[i] is non positive we continue

i = 1
nums[i] = 4
index = 4-1 = 3
Since nums[index] != nums[i], we swap elements
nums = [-1, 1, 3, 4]

i = 1
nums[i] = 1
index = 1-1 = 0
Since nums[index] != nums[i], we swap elements
nums = [1, -1, 3, 4]

i = 1
nums[i] = -1
Since nums[i] is non positive we continue

i = 2
nums[i] = 3
index = 3-1 = 2
Since nums[index] == nums[i], we continue

i = 3
nums[i] = 4
index = 4-1 = 3
Since nums[index] == nums[i], we continue

i = 4
Loop is over
nums = [1, -1, 3, 4]

We check for position that is i+1 != nums[i]
Since 2 is not at position, 2 is the first missing positive number
Thus the answer is 2

Here is the Python code for the solution:

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        i = 0

        while i < n:
            # if nums[i] is non positive or bigger than n+1 we continue
            if nums[i] <= 0 or nums[i] > n:
                i += 1
                continue

            index = nums[i] - 1
            # if nums[i] and nums[index] is different swap elements
            if nums[i] != nums[index]:
                nums[i], nums[index] = nums[index], nums[i]
            else:
                i += 1
        
        # running for loop to see first missing positive
        for i in range(len(nums)):
            if nums[i] != i+1:
                return i+1
        
        return n+1

Time Complexity and Space Complexity

Time Complexity: $O(n)$ since we’re running for loop of the array 2 times $O(2n)$

Space Complexity: $O(1)$ since we’re manipulating the array that is given