19. Kth Missing Positive Number in a Sorted Array

The problem can be found at the following link: Question Link

Problem Description

Given a sorted array of distinct positive integers arr[] and an integer k, find the kth positive number that is missing from the array.

Example

Input:

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

Output:

9

Explanation: The missing numbers are 1, 5, 6, 8, 9, 10, .... The 5th missing number is 9.

Input:

arr = [3, 5, 9, 10, 11, 12]
k = 2

Output:

2

Explanation: The missing numbers are 1, 2, 4, 6, 7.... The 2nd missing number is 2.

Constraints:

• $1 <= arr.size() <= 10^5$

• $1 <= k <= 10^5$

• $1 <= arr[i]<= 10^6$

My Approach

Binary Search

1. Key Observations:

   • For an index i in arr, the number of missing positive integers up to arr[i] is given by: $[ \text{Missing Numbers} = arr[i] - (i + 1) $]

   • If this count is less than k, the kth missing number lies after arr[i]. Otherwise, it lies before arr[i].

2. Steps:

   • Use binary search over the array to find the smallest index i such that the count of missing numbers is at least k.

   • Once located, calculate the kth missing number using: $[ \text{Result} = \text{Index} + k ]$

3. Edge Case:

   • If all missing numbers are after the largest element in arr, return: $[ arr[-1] + (k - \text{Missing Numbers till end}) ]$

Time and Auxiliary Space Complexity

Expected Time Complexity: $[ O(log n) $] where n is the size of the array, as binary search is used to locate the position.

Expected Auxiliary Space Complexity: $[ O(1) $] since no additional data structures are used apart from a few variables.

Code (C)

int kthMissing(int* arr, int n, int k) {
    int lo = 0, hi = n;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] - (mid + 1) < k) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    return lo + k;
}

Code (C++)

class Solution {
public:
    int kthMissing(vector<int>& arr, int k) {
        int lo = 0, hi = arr.size();
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (arr[mid] - (mid + 1) < k)
                lo = mid + 1;
            else
                hi = mid;
        }
        return lo + k;
    }
};

Code (Java)

class Solution {
    public int kthMissing(int[] arr, int k) {
        int lo = 0, hi = arr.length;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (arr[mid] - (mid + 1) < k) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return lo + k;
    }
}

Code (Python)

class Solution:
    def kthMissing(self, arr, k):
        lo, hi = 0, len(arr)
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if arr[mid] - (mid + 1) < k:
                lo = mid + 1
            else:
                hi = mid
        return lo + k

Contribution and Support

For discussions, questions, or doubts related to this solution, please visit my LinkedIn:- Any Questions. Thank you for your input; together, we strive to create a space where learning is a collaborative endeavor.

⭐ Star this repository if you find it helpful or intriguing! ⭐

---

📍Visitor Count