first missing positive

Guri Bee

3 min read

·

19-10-2024

1

0

Share

Finding the First Missing Positive: A Deep Dive into a Classic Algorithm Problem

The "First Missing Positive" problem is a popular coding challenge that often appears in technical interviews. It's a great way to demonstrate your understanding of algorithms and data structures, particularly in the context of arrays. In this article, we'll delve into the problem, analyze different approaches, and explore how to solve it efficiently.

Problem Statement

Given an unsorted array of integers, find the first missing positive integer. The array may contain duplicates, negative numbers, and zeros.

Example:

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

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

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

Approaches

There are multiple approaches to solving this problem. Here are two popular methods:

1. Using a Set:

This approach involves creating a set of all positive numbers present in the array. Then, we iterate from 1 to the length of the array plus 1, checking if each number is present in the set. The first number not found in the set is the missing positive integer.

Example:

def first_missing_positive_set(nums):
  """
  Finds the first missing positive integer using a set.

  Args:
    nums: A list of integers.

  Returns:
    The first missing positive integer.
  """

  positive_nums = set(nums)
  for i in range(1, len(nums) + 2):
    if i not in positive_nums:
      return i

  return len(nums) + 1

Pros:

• Simple to understand and implement.

Cons:

• Potentially inefficient for large arrays due to the set creation and iteration.

2. In-place Modification:

This approach uses the array itself to keep track of which numbers are present. We iterate through the array, using the absolute value of each number as an index. If we encounter a positive number, we change the sign of the element at that index. If the element at that index is already negative, we know that the number is already present.

Example:

def first_missing_positive(nums):
  """
  Finds the first missing positive integer using in-place modification.

  Args:
    nums: A list of integers.

  Returns:
    The first missing positive integer.
  """

  n = len(nums)

  # Mark the presence of positive numbers by changing their sign
  for i in range(n):
    if 1 <= nums[i] <= n:
      index = abs(nums[i]) - 1
      if nums[index] > 0:
        nums[index] *= -1

  # Find the first positive number
  for i in range(n):
    if nums[i] > 0:
      return i + 1

  return n + 1

Pros:

• Efficient: Only one pass through the array.
• Constant space complexity.

Cons:

• Can be less intuitive to understand than the set approach.

Choosing the Right Approach

The choice of approach depends on the specific requirements of your problem. If space efficiency is critical, the in-place modification method is preferred. However, if ease of implementation is more important, the set approach might be a better choice for smaller arrays.

Additional Insights

• Handling Duplicates: The in-place modification approach elegantly handles duplicates. If a number appears multiple times, its index will be marked negative only once.
• Handling Zeros: The algorithm gracefully handles zeros because they are not considered positive numbers.
• Edge Cases: The algorithm gracefully handles cases where the input array is empty or all numbers are negative. In these cases, the first missing positive is 1.

Conclusion

The "First Missing Positive" problem is a valuable exercise in understanding arrays and algorithms. By understanding different approaches and analyzing their trade-offs, you can choose the most suitable solution for your specific scenario. This problem also highlights the importance of in-place modification techniques for achieving both space and time efficiency.

References:

• LeetCode
• GitHub Repository (Author: TheAlgorithms)