Problem Description

You are given a sorted array of distinct positive integers arr and an integer k. Your task is to find the k-th missing positive integer that is not present in arr.

• arr contains only positive integers, sorted in strictly increasing order.
• Each element is unique; no duplicates.
• You need to find the k-th missing positive number (i.e., the k-th smallest positive integer that does not appear in arr).

Constraints:

• There is always exactly one valid answer for the input.
• You should not reuse elements; only count numbers missing from arr.

Thought Process

At first glance, you might want to generate all positive integers, skipping those in arr, and count until you reach the k-th missing number. However, this brute-force approach is inefficient if k is large or arr is long.

By thinking more deeply, we realize that since arr is sorted and contains only positive numbers, we can efficiently count how many numbers are missing up to each position in arr. The difference between the current value and its index (plus one) tells us how many numbers are missing before that position. This insight allows us to jump directly to the answer without checking every integer.

So, the key is to:

• Calculate how many numbers are missing up to each index.
• Find where the k-th missing number fits in relation to arr.
• Decide what to return based on whether k is before, within, or after the last element of arr.

Solution Approach

Let's break down the steps to solve the problem efficiently:

1. Understand the "missing count" at each index:
   • For any arr[i], the number of missing positive integers before it is arr[i] - (i + 1).
   • For example, if arr[0] = 2, then 2 - 1 = 1 number is missing before arr[0] (which is 1).
2. Iterate through arr and track missing numbers:
   • For each index, check if the number of missing numbers up to that point is less than k.
   • If not, it means the k-th missing number is between arr[i-1] and arr[i].
3. Decide which case applies:
   • If k is greater than the number of missing numbers before the last element, then the answer is beyond the last element of arr: arr[-1] + (k - missing_before_last).
   • Otherwise, the answer is between two elements: arr[i-1] + (k - missing_before_prev).
4. Optimization:
   • Since arr is sorted, we can use binary search to find the first index where the number of missing numbers is greater than or equal to k, which makes the solution much faster for large inputs.

This approach ensures we never scan more than necessary, making the solution efficient and elegant.

Example Walkthrough

Let's use arr = [2, 3, 4, 7, 11] and k = 5 as our example.

1. Calculate missing numbers at each index:
   • At index 0: 2 - 1 = 1 (missing: 1)
   • At index 1: 3 - 2 = 1 (still just 1 missing: 1)
   • At index 2: 4 - 3 = 1 (still just 1 missing: 1)
   • At index 3: 7 - 4 = 3 (missing: 1,5,6; so total missing up to here is 3)
   • At index 4: 11 - 5 = 6 (missing: 1,5,6,8,9,10; total missing up to here is 6)
2. Find where the 5th missing number fits:
   • At index 4, 6 numbers are missing (which includes our 5th).
   • At index 3, only 3 numbers are missing (so, 5th missing is between index 3 and 4).
3. Compute the answer:
   • Number of missing numbers before arr[3]: 3
   • So, the 5th missing is arr[3] + (k - missing_before_3) = 7 + (5 - 3) = 9
4. Final answer: 9

Time and Space Complexity

• Brute-force approach:
  • Iterate from 1 upwards, skip numbers in arr, and count missing until k is reached.
  • Time Complexity: O(k + n) in the worst case (if all numbers are missing or k is very large).
  • Space Complexity: O(1) extra space.
• Optimized approach (using binary search):
  • Use binary search to find the correct index in arr.
  • Time Complexity: O(log n), since we perform binary search on arr of length n.
  • Space Complexity: O(1), as we only use a few variables.

Summary

The key insight is that the number of missing numbers up to each index in arr can be calculated directly using arr[i] - (i + 1). By leveraging binary search, we can efficiently pinpoint where the k-th missing positive integer falls, making the solution both fast and elegant. This approach avoids unnecessary iteration and demonstrates the power of mathematical reasoning and search algorithms in array problems.

Code Implementation

class Solution:
    def findKthPositive(self, 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
      

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

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

var findKthPositive = function(arr, k) {
    let left = 0, right = arr.length - 1;
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        let missing = arr[mid] - (mid + 1);
        if (missing < k) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return left + k;
};