Kth Missing Positive Number

Problem Description

Given an array arr of positive integers sorted in a strictly increasing order, and an integer k, return the kth positive integer that is missing from this array.

Key Insights

• The positive integers start from 1 and increase sequentially.
• The missing integers can be found by comparing the expected sequence of integers with the numbers present in the array.
• We can maintain a count of missing integers and find the kth missing number by iterating through the numbers.
• A binary search approach can optimize the search for larger inputs.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve this problem, we can use a two-pointer technique or a linear scan approach. We will iterate through all positive integers starting from 1, keeping track of how many positive integers are missing as we compare them to the elements in the given sorted array. When the count of missing integers reaches k, we can return that number.

1. Initialize a pointer for the current positive integer starting from 1.
2. Initialize a count for missing integers.
3. Iterate through the array and compare each element with the current positive integer.
4. If the current positive integer is not present in the array, increment the missing count.
5. If the missing count equals k, return the current positive integer.
6. If we reach the end of the array, continue iterating until we find the k missing number.

Code Solutions