5 Best Ways to Find the First Positive Missing Integer in a Range in Python

Rate this post

πŸ’‘ Problem Formulation: Given an unsorted array of integers, the task is to find the smallest positive integer that is missing from the array. For instance, with an input array [3, 4, -1, 1], the desired ouput is 2, since it’s the smallest missing positive integer that doesn’t appear in the list.

Method 1: Sorting and Linear Traversal

This method involves first sorting the array, and then scanning it to identify the missing integer. Functionally, you’d want to skip non-positive integers, scan through the sorted list, and look for gaps in the sequence of positive numbers.

Here’s an example:

def find_missing_integer(arr):
    arr.sort()
    smallest_int = 1
    for num in arr:
        if num == smallest_int:
            smallest_int += 1
    return smallest_int

print(find_missing_integer([3, 4, -1, 1]))

The output of this code snippet:

2

In this code, we first sort the array which takes O(n log n) time and then traverse it to find the first gap in positive numbers, defining our missing integer. This is a straightforward approach but might not be the best in terms of efficiency due to the sorting step.

Method 2: Using a HashSet

By using a HashSet, we can store the numbers present in the array and then iterate through positive integers starting from 1, checking the set to find the first number that is missing. HashSet operations have an average time complexity of O(1), making the overall algorithm O(n).

Here’s an example:

def find_missing_integer(arr):
    nums_set = set(arr)
    smallest_int = 1
    while smallest_int in nums_set:
        smallest_int += 1
    return smallest_int

print(find_missing_integer([3, 4, -1, 1]))

The output of this code snippet:

2

This approach skips the sorting process by leveraging a HashSet to rapidly check for the presence of numbers. This makes it more efficient, especially for larger arrays, as it runs in linear time.

Method 3: In-Place Hashing

In-Place hashing avoids using extra space and instead tries to hash values within the array by placing each number at its correct index if possible. The first index which does not have the correct number indicates the missing integer.

Here’s an example:

def find_missing_integer(arr):
    for i in range(len(arr)):
        while 1 <= arr[i] <= len(arr) and arr[i] != arr[arr[i]-1]:
            arr[arr[i]-1], arr[i] = arr[i], arr[arr[i]-1]
    for i in range(len(arr)):
        if arr[i] != i + 1:
            return i + 1
    return len(arr) + 1

print(find_missing_integer([3, 4, -1, 1]))

The output of this code snippet:

2

While this method operates in O(n) time without requiring extra space, its complexity lies in the need for understanding and correctly implementing index-based swapping, which can be error-prone for complex scenarios.

Method 4: Using Python’s Set Operations

Python sets provide a simple method to solve this problem by creating a set of all numbers from 1 to N (where N is the length of the array) and then subtracting the set of numbers actually present in the array. The first integer in the resulting set is the missing one.

Here’s an example:

def find_missing_integer(arr):
    max_num = len(arr) + 1
    all_nums = set(range(1, max_num))
    arr_set = set(arr)
    missing_numbers = all_nums - arr_set
    return min(missing_numbers)

print(find_missing_integer([3, 4, -1, 1]))

The output of this code snippet:

2

This method is intuitive and leverages Python’s powerful set operations. It’s particularly clear and easy to write. However, it may not be as efficient as the in-place hashing due to the need to generate a large set if the array is significantly large.

Bonus One-Liner Method 5: Using Generators and Next

For a succinct solution, Python’s next function can be combined with a generator that iterates over the positive integers, leveraging the set to exclude those which are present. This code showcases Python’s ability to express complex operations in a single, expressive line.

Here’s an example:

def find_missing_integer(arr):
    arr_set = set(arr)
    return next(filter(lambda i: i not in arr_set, range(1, len(arr) + 2)))

print(find_missing_integer([3, 4, -1, 1]))

The output of this code snippet:

2

The one-liner filters out the smallest missing number using a combination of filter, lambda, and the next function to find the first integer that is not in the set of numbers from the array. While concise, readability can be compromised, which might be a disadvantage during code reviews or collaborations.

Summary/Discussion

  • Method 1: Sorting and Linear Traversal. Simple and straightforward. Not the most efficient due to sorting step.
  • Method 2: Using a HashSet. Efficient with an average case time complexity of O(n). Uses extra space for the set.
  • Method 3: In-Place Hashing. Space-efficient and fast. Code is complex and less readable.
  • Method 4: Using Python’s Set Operations. Intuitive and easy to write. Potentially less efficient for large input arrays.
  • Bonus Method 5: Using Generators and Next. Elegant one-liner. Readability may suffer which isn’t ideal for maintenance or collaboration.