Leetcode 1539. Kth Missing Positive Number

Let's understand what we're being asked to do. We have a sorted array like [2, 3, 4, 7, 11] and need to find the k-th positive integer that's missing from this sequence.

For example, if k=5, let's trace which positive integers are missing: 1 is missing (1st missing), 5 is missing (2nd missing), 6 is missing (3rd missing), 8 is missing (4th missing), 9 is missing (5th missing). So the answer is 9.

Key insight from the problem: At any index i, the value arr[i] tells us how many positive integers exist up to that point. Since indices are 0-based, there are i+1 positions. Therefore, arr[i] - (i+1) gives us the count of missing numbers up to index i.

Important constraint: The array is sorted in strictly increasing order with positive integers only.

Edge cases to consider: What if k is smaller than all missing numbers before the first element? What if k is larger than all missing numbers within the array range?

The straightforward approach is to iterate through the array and count missing numbers at each position using the formula arr[i] - (i+1). Once we find an index where the count of missing numbers is greater than or equal to k, we know the k-th missing number lies in that interval. We can then calculate it directly using the previous index's information. This approach is simple but doesn't fully exploit the sorted property of the missing counts.

def find_kth_missing(arr, k):
    """
    Find the k-th positive integer missing from a sorted array.
    Brute force approach: iterate through array and count missing numbers.
    """
    # Track count of missing numbers found so far
    missing_count = 0
    # Current positive integer we're checking
    current = 1
    # Index in the array
    index = 0
    n = len(arr)
    
    # Iterate through positive integers
    while missing_count < k:
        # If we've exhausted the array or current is less than arr[index]
        if index >= n or current < arr[index]:
            # Current number is missing
            missing_count += 1
            # If this is the k-th missing number, return it
            if missing_count == k:
                return current
        else:
            # Current number exists in array, move to next array element
            index += 1
        
        # Move to next positive integer
        current += 1
    
    return -1

At each index i, we can calculate how many numbers are missing up to that point using the formula arr[i] - (i+1).

For example, at index 2 with value arr[2]=4, we know there should be 3 numbers (indices 0,1,2), but the value is 4, meaning 4-3=1 number is missing before this position.

This monotonically increasing count of missing numbers means we can locate which interval contains the k-th missing number.

Since the count of missing numbers increases as we move right through the array, we can use this property to eliminate half the search space at each step.

If the missing count at the middle is less than k, the k-th missing number must be to the right. If it's greater than or equal to k, it must be to the left or at that position.

This transforms a linear scan into a logarithmic search, reducing time from O(n) to O(log n).

Think of the array as creating 'gaps' between consecutive integers. Each gap represents missing numbers.

For [2, 3, 4, 7, 11]: gap before 2 has 1 missing (1), gap between 4 and 7 has 2 missing (5, 6), gap between 7 and 11 has 3 missing (8, 9, 10).

The cumulative count of missing numbers up to each position is sorted, which is exactly what we need for efficient searching. We're essentially searching for the right gap that contains our k-th missing number.

The optimal approach uses binary search on the array to find the interval containing the k-th missing number. At each step, calculate the missing count at the middle index using arr[mid] - (mid+1). If this count is less than k, the k-th missing number must be to the right, so search the right half. Otherwise, search the left half. Once we find the correct interval (or determine it's before/after the array), we calculate the k-th missing number using the formula based on the boundary index and remaining missing count.

def find_kth_missing(arr, k):
    """
    Find the k-th missing positive integer from a sorted array.
    Uses binary search on missing count: arr[i] - (i+1).
    """
    # Binary search initialization
    left = 0
    right = len(arr) - 1
    
    # Binary search to find the interval containing k-th missing
    while left <= right:
        mid = (left + right) // 2
        # Calculate missing count up to index mid
        missing_count = arr[mid] - (mid + 1)
        
        # If missing count < k, search right half
        if missing_count < k:
            left = mid + 1
        else:
            # Search left half
            right = mid - 1
    
    # Calculate k-th missing number
    # If left == 0, k-th missing is before array: k
    # Otherwise: arr[right] + (k - missing_at_right)
    if left == 0:
        return k
    
    missing_at_right = arr[right] - (right + 1)
    return arr[right] + (k - missing_at_right)

• Missing element formula: In a sorted array starting from 1, the count of missing numbers up to index i is `arr[i] - (i + 1)`. This mathematical insight transforms a counting problem into a searchable property, enabling binary search on an implicit monotonic function.
• Binary search on derived properties: You don't need to binary search on array values directly - search on computed properties like "missing count". The key is recognizing that `missing_count(i)` is monotonically increasing, making it binary-searchable even though we're not searching for a target value.
• Interval-based answer computation: Once binary search identifies the interval where the k-th missing number falls (between indices), calculate it as `left + k` or `arr[right] - (missing_at_right - k)`. The missing number exists in the gap, not in the array itself.
• Off-by-one in array indexing: A critical mistake is forgetting that `arr[i]` should contain value `i+1` if nothing is missing (not `i`). Always use `arr[i] - (i + 1)` for missing count, and remember the answer when k exceeds all missing numbers is `arr[n-1] + (k - missing_at_end)`.
• O(log n) vs O(n) decision point: When you need the k-th element of something not explicitly stored but derivable from a sorted structure, consider binary search. The linear scan `O(n)` solution works but misses that "missing count" increases predictably, making logarithmic search possible.
• Gap analysis in sequences: This pattern applies to database pagination (finding the n-th available slot), memory allocation (locating free blocks), scheduling (finding available time slots), and version control (identifying missing commits in a sequence) - anywhere you track what's present to infer what's absent.