First Missing Positive

This problem is about finding the smallest missing positive integer in an unsorted array with the constraint that the algorithm should run in O(n) time and use O(1) auxiliary space.

Approach

The idea is to use the given array itself to arrange the elements in such a way that if an element nums[i] is positive and less than the length of the array, then it should be put at its correct position (i.e., nums[nums[i] - 1]).

Here’s a step-by-step approach:

  1. Iterate through the array: For each element, if it is positive and less than or equal to the length of the array, and it’s not already at its correct position, swap it with the element at its target position.
  2. Find the first mismatch: Iterate through the modified array, and find the first element that doesn’t match its index. The missing positive integer is index + 1.
  3. Return the result: If no mismatch is found, return the length of the array + 1 as the missing integer.

Implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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

        for i in range(n):
            while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
                nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]

        for i in range(n):
            if nums[i] != i + 1:
                return i + 1

        return n + 1

Insights and Key Takeaways

  • The solution cleverly uses the array itself as a storage to keep track of the presence of integers.
  • By putting the numbers in their correct positions (if they fall within the range [1, n]), we can quickly find the missing integer without extra space.
  • The while loop ensures that the swapping continues until an element is placed in its correct position or an out-of-range element is encountered.
  • The time complexity is O(n) since each element is swapped at most once.
  • The space complexity is O(1), as required, since we only use a constant amount of extra space.
  • This problem is a great example of an in-place algorithm that leverages the structure of the input to achieve space efficiency.

10 Prerequisite LeetCode Problems

“First Missing Positive” requires an understanding of array manipulation and hashing. Here are 10 simpler problems to build the necessary skills:

  1. “Two Sum” (LeetCode Problem #1): This problem helps to understand the usage of hash maps, which can be useful for the “First Missing Positive” problem.

  2. “Remove Duplicates from Sorted Array” (LeetCode Problem #26): This problem introduces basic array manipulation techniques.

  3. “Find All Numbers Disappeared in an Array” (LeetCode Problem #448): This problem introduces the concept of using array indices as a form of in-place hashing.

  4. “Contains Duplicate” (LeetCode Problem #217): This problem provides further practice with using array elements for in-place hashing.

  5. “Missing Number” (LeetCode Problem #268): This problem is directly related to finding missing elements in an array.

  6. “Single Number” (LeetCode Problem #136): This problem helps to understand XOR operations which can be beneficial in many array problems.

  7. “Find the Duplicate Number” (LeetCode Problem #287): It introduces the concept of detecting duplications in an array which is important for “First Missing Positive”.

  8. “Rotate Array” (LeetCode Problem #189): This problem provides good practice for array manipulation, especially for understanding how to rearrange elements within an array.

  9. “Move Zeroes” (LeetCode Problem #283): This problem also helps to understand in-place modifications in arrays.

  10. “Find All Duplicates in an Array” (LeetCode Problem #442): This problem provides further practice with using array indices as a form of in-place hashing, similar to what’s required in “First Missing Positive”.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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

        for i in range(n):
            if nums[i] <= 0 or nums[i] > n:
                nums[i] = n + 1
        for i in range(n):
            if abs(nums[i]) > n:
                continue
            nums[abs(nums[i]) - 1] = -abs(nums[abs(nums[i]) - 1])
        for i in range(n):
            if nums[i] > 0:
                return i + 1
        return n + 1

Problem Classification

This problem deals with finding the first missing positive integer in an unsorted integer array. Since we are examining the properties of numbers and identifying missing elements, it’s categorized as Number Properties Analysis.

The problem is about finding the first missing positive number in a list of numbers that are not in order. Since we’re looking at the properties of numbers and finding what’s missing, this is Number Analysis.

Language Agnostic Coding Drills

  1. Working with Lists/Arrays: Understanding the basic operations with lists/arrays: accessing elements, iterating over the list, updating elements based on conditions.

  2. Understanding Conditional Statements: The code uses simple conditional statements to check for certain conditions and perform operations based on those.

  3. Basic Arithmetic Operations: The code uses arithmetic operations to manipulate indices and array elements.

  4. Understanding the concept of in-place operations: The problem is solved in constant space complexity. Understanding how in-place operations work, where the input array is updated during each operation rather than creating new data structures.

  5. Understanding absolute value function: The code uses the absolute value function to maintain the numbers in positive format for the comparison and then making them negative for marking as visited.

  6. Understanding the concept of Marking elements in the array: The problem is solved using the logic where the existence of a number in the array is marked by making the number at its index negative. This is a common technique in solving such problems.

  7. Identifying the first missing positive integer: The final step involves iterating over the array to identify the first index which is positive indicating the missing smallest positive integer.

The problem solving approach:

  1. Step 1 - Understanding the problem statement: We need to find the first missing positive integer from the list of integers.

  2. Step 2 - Preprocessing the array: Go through the array, and all the non-positive numbers and numbers greater than the length of the array are replaced with a constant number which is greater than the length of the array.

  3. Step 3 - Marking numbers in the array: Go through the array again, for every number encountered check if the absolute value is greater than the length of the array. If not, make the number at its index position negative.

  4. Step 4 - Finding the first missing positive integer: Finally, go through the array and find the first index which has a positive number. The first missing positive number will be index+1. If no such index is found, return length+1.

This algorithm works in O(N) time and uses O(1) space, by using the indices of the array itself to keep track of the numbers that are present.

Targeted Drills in Python

  1. Working with Lists/Arrays: Understand how to access, iterate, and modify elements in a list.

    1
2
3
4
5

    arr = [1, 2, 3, 4, 5]
for i in range(len(arr)):
    print(arr[i])
    arr[i] = arr[i]*2
print(arr)

  2. Understanding Conditional Statements: Write a function that takes an array and a number as inputs, and returns a new array with all elements greater than the number doubled.

    1
2
3
4
5

    def double_greater(arr, num):
    for i in range(len(arr)):
        if arr[i] > num:
            arr[i] = arr[i]*2
    return arr

  3. Basic Arithmetic Operations: Practice simple arithmetic operations by writing a function that calculates the mean of a list.

    1
2

    def mean(arr):
    return sum(arr)/len(arr)

  4. Understanding the concept of in-place operations: Write a function that reverses a list in-place.

    1
2
3
4
5

    def reverse_list(nums):
    left, right = 0, len(nums) - 1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left, right = left + 1, right - 1

  5. Understanding absolute value function: Write a function that replaces all elements in a list with their absolute value.

    1
2
3
4

    def absolute_list(nums):
    for i in range(len(nums)):
        nums[i] = abs(nums[i])
    return nums

  6. Understanding the concept of Marking elements in the array: Write a function to mark an element in an array as visited by negating it.

    1
2
3

    def mark_visited(arr, i):
    arr[i] = -arr[i]
    return arr

  7. Identifying the first missing positive integer: Write a function that finds the first positive integer missing from the list. (This is a simplified version of the final problem where the list only contains positive integers)

    1
2
3
4
5
6
7
8
9

    def first_missing_positive(nums):
    if not nums:
        return 1
    nums.sort()
    smallest_int = 1
    for num in nums:
        if num == smallest_int:
            smallest_int += 1
    return smallest_int

These drills will help you understand the basics required to solve the final problem. You can start by solving these simple problems and then gradually move to solve the final problem. It is suggested to understand each of these drills as they form the building blocks for solving complex problems.