Kth Missing Positive Number

Share

Find the kth missing positive integer from a sorted array of distinct positive integers.

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

Solution Approach

Binary search: at index i, missing count = arr[i]-(i+1). Find first index where missing >= k.

  • Binary search on arr
  • At mid: missing = arr[mid] - (mid+1)
  • If missing < k: search right
  • Else search left
  • Result = left + k (left is the first index where missing >= k)
Java
public int findKthPositive(int[] arr, int k) {
    int left = 0, right = arr.length;
    while (left < right) {
        int mid = (left + right) / 2;
        if (arr[mid] - (mid + 1) < k) left = mid + 1;
        else right = mid;
    }
    return left + k;
}
  • Time Complexity: O(log n)
  • Space Complexity: O(1)