Leetcode – Kth Missing Positive Number Solution

Spread the love

In algorithmic challenges, especially in coding interviews and competitive programming, understanding the problem statement thoroughly is the first step toward coming up with an optimal solution. The problem “Kth Missing Positive Number” asks us to find the Kth missing positive number in a given list of numbers.

Problem Description:

Given an array arr of positive integers sorted in a strictly increasing order, and an integer k.

Find the kth positive integer that is missing from this array.

Examples:

Example 1:

Input: arr = [2,3,4,7,11], k = 5

Output: 9

Example 2:

Input: arr = [1,2,3,4], k = 2

Output: 6

Approaches to Solving the Problem

1. Brute-force Approach

One of the most straightforward ways to solve this problem is by employing a brute-force method where we simply iterate from 1 upwards, checking whether each number exists in arr. We keep a count of how many numbers we’ve found that are missing from arr, and when this count reaches k, we return the current number.

Here’s how you can implement this in Python:

def findKthPositive(arr, k):
    count = 0
    num = 1
    
    while count < k:
        if num not in arr:
            count += 1
            if count == k:
                return num
        num += 1

Time Complexity

The time complexity for this approach is O(n×m), where n is the value of the Kth missing positive number and mm is the length of arr.

2. Optimized Approach Using Two Pointers

A more optimized way of solving this problem is by using two pointers to traverse the array arr and the sequence of natural numbers. Since arr is sorted, we can do this in a single pass.

Here’s how:

def findKthPositive(arr, k):
    i, j = 0, 1
    while k > 0:
        if i < len(arr) and arr[i] == j:
            i += 1
        else:
            k -= 1
        if k > 0:
            j += 1
    return j

Time Complexity

The time complexity for this approach is O(n+m), where n is the length of arr, and m is the value of the Kth missing positive number. This is more efficient than the brute-force approach.

3. Using Binary Search

Since arr is sorted, we can also make use of binary search to find the range where the Kth missing positive number will reside.

Here’s the Python code for it:

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

Time Complexity

The time complexity for this approach is O(log ⁡n), where n is the length of arr.

Comparison of Approaches

Conclusion

The problem of finding the Kth missing positive number can be solved using multiple approaches, each with its own trade-offs in terms of time and space complexity. By understanding the underlying mechanics of each approach, one can choose the most appropriate method for solving this problem efficiently.

For smaller datasets or less frequent queries, the brute-force or two-pointer approaches may be sufficient. However, for larger datasets or more frequent queries, the binary search approach will be more efficient.

Leave a Reply