5 Best Ways to Find the Kth Missing Positive Number in an Array in Python

Rate this post

πŸ’‘ Problem Formulation: The challenge lies in identifying the kth missing positive integer in a given sorted array. For instance, if the input array is [2, 3, 4, 7, 11] and k is 5, the desired output is 9, since the missing positive integers are [1, 5, 6, 8, 9], and the 5th missing positive integer is 9.

Method 1: Sequential Search

This method involves scanning the given array sequentially while keeping track of missing positive integers. Functionally, it steps through the array and the full range of positive integers concurrently, counting any discrepancies between the two as missing integers until the kth missing number is found.

Here’s an example:

def find_kth_missing(arr, k):
    missing_count = 0
    current_num = 1
    i = 0
    while missing_count < k:
        if i < len(arr) and arr[i] == current_num:
            i += 1
        else:
            missing_count += 1
            if missing_count == k:
                return current_num
        current_num += 1

print(find_kth_missing([2, 3, 4, 7, 11], 5))

Output:

9

This function find_kth_missing iterates through the array alongside a current_num counter, which represents the current positive number we are checking. When current_num matches an array element, both pointers are incremented. If not, the missing_count increments and the function eventually returns the kth missing number.

Method 2: Binary Search

Binary search can be applied by first defining how many positive numbers are missing up to a certain index in the array, and then using this information to find the kth missing number. This is more efficient than Method 1 for large arrays, as it reduces the time complexity to O(log n).

Here’s an example:

def find_kth_missing_binary_search(arr, k):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] - mid - 1 < k:
            left = mid + 1
        else:
            right = mid - 1
    return left + k

print(find_kth_missing_binary_search([2, 3, 4, 7, 11], 5))

Output:

9

The find_kth_missing_binary_search function performs a binary search to locate the section of the array where the kth missing number falls. It utilizes the fact that if there are no missing numbers, the value at index i should be i + 1.

Method 3: Set Difference

Python’s set data structure can be used to find the kth missing positive number by creating a set from the array and another set for the range of numbers expected to contain the kth missing positive. The set difference reveals all missing numbers which can be indexed to find the kth missing.

Here’s an example:

def find_kth_missing_set(arr, k):
    set_diff = list(set(range(1, arr[-1] + k + 1)) - set(arr))
    return set_diff[k-1]

print(find_kth_missing_set([2, 3, 4, 7, 11], 5))

Output:

9

In this find_kth_missing_set function, the set difference method removes all the elements from a theoretical complete list that are found in the given array, leaving behind only the missing elements. The (k-1) index is then used to return the kth missing number.

Method 4: Using Extra List

This method involves creating an auxiliary list to record the missing numbers up to the kth missing one. The array is iterated, and whenever a gap in the sequence is found, it is filled in the auxiliary list until the list contains k missing numbers.

Here’s an example:

def find_kth_missing_list(arr, k):
    missing_numbers = []
    current_num = 1
    i = 0
    while len(missing_numbers) < k:
        if i < len(arr) and arr[i] == current_num:
            i += 1
        else:
            missing_numbers.append(current_num)
        current_num += 1
    return missing_numbers[-1]

print(find_kth_missing_list([2, 3, 4, 7, 11], 5))

Output:

9

In this find_kth_missing_list method, each iteration looks for missing numbers and appends them to the missing_numbers list, which grows until it reaches size k. The last element is the kth missing number.

Bonus One-Liner Method 5: Using List Comprehension and itertools

List comprehension in tandem with Python’s itertools can provide a sleek one-liner solution. By leveraging itertools.count to generate an infinite sequence of integers, and list comprehension to filter out elements not in the array, we achieve an elegant solution that scales well.

Here’s an example:

import itertools

def find_kth_missing_oneliner(arr, k):
    return next(itertools.islice((x for x in itertools.count(1) if x not in arr), k - 1, k))

print(find_kth_missing_oneliner([2, 3, 4, 7, 11], 5))

Output:

9

This one-liner find_kth_missing_oneliner uses a generator expression to iterate over an infinite sequence of positive integers, excluding those present in the array. The kth element of this generator is then plucked out using itertools.islice.

Summary/Discussion

  • Method 1: Sequential Search. Simple and intuitive. Works well for small arrays. Can be inefficient for large arrays where k is also large.
  • Method 2: Binary Search. Efficient for large arrays. Requires understanding of binary search. May not be as intuitive for beginners.
  • Method 3: Set Difference. Pythonic and concise. Performance hit with larger ranges due to set operations.
  • Method 4: Using Extra List. Easy to understand. Extra space used is proportional to k which isn’t efficient for very large k.
  • Method 5: One-Liner with itertools. Elegant and pythonic. Can be less readable for those not familiar with itertools or generator expressions.