Problem

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.

Examples

Example 1:

1
2
3
4
5

Input:
arr = [2,3,4,7,11], k = 5
Output:
 9
Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,...]. The 5th missing positive integer is 9.

Example 2:

1
2
3
4
5

Input:
arr = [1,2,3,4], k = 2
Output:
 6
Explanation: The missing positive integers are [5,6,7,...]. The 2nd missing positive integer is 6.

Solution

Method 1 – Binary Search for Missing Count

Intuition

Since the array is strictly increasing and sorted, we can efficiently determine how many positive numbers are missing up to any index. By comparing the value at each index with its expected value (index + 1), we can count the missing numbers. Binary search helps us quickly find the smallest index where the count of missing numbers is at least k.

Approach

  1. For each index i, the number of missing numbers before arr[i] is arr[i] - (i + 1).
  2. Use binary search to find the smallest index where the missing count is at least k.
  3. If all missing numbers are before the array ends, the answer is k + the length of the array.
  4. Otherwise, the answer is arr[left - 1] + (k - missing count at left - 1).

Complexity

  • ⏰ Time complexity: O(log n), because we use binary search over the array.
  • 🧺 Space complexity: O(1), as we use only a few variables for computation.
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
    int findKthPositive(vector<int>& arr, int k) {
        int left = 0, right = arr.size();
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] - (mid + 1) < k) left = mid + 1;
            else right = mid;
        }
        return left + k;
    }
};
Java
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    public int findKthPositive(int[] arr, int k) {
        int left = 0, right = arr.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] - (mid + 1) < k) left = mid + 1;
            else right = mid;
        }
        return left + k;
    }
}
Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def findKthPositive(self, arr: list[int], k: int) -> int:
        left, right = 0, len(arr)
        while left < right:
            mid = (left + right) // 2
            if arr[mid] - (mid + 1) < k:
                left = mid + 1
            else:
                right = mid
        return left + k