Find the Kth Missing Positive Number Using Binary Search

Problem Overview

You are given a sorted array of distinct positive integers, arr[], and a positive integer k.

Your task is to find the kth missing positive number that does not appear in arr[].

Example 1

Input

arr = [2, 3, 4, 7, 11]
k = 5

Output

Explanation

Missing numbers:

1, 5, 6, 8, 9, 10, ...

The 5th missing number is:

Example 2

Input

arr = [1, 2, 3]
k = 2

Output

Explanation

Missing numbers:

4, 5, 6, ...

The 2nd missing number is:

Example 3

Input

arr = [3, 5, 9, 10, 11, 12]
k = 2

Output

Explanation

Missing numbers:

1, 2, 4, 6, ...

The 2nd missing number is:

Constraints

1 ≤ arr.length ≤ 10^5
1 ≤ k ≤ 10^5
1 ≤ arr[i] ≤ 10^6
The array is sorted in ascending order.
All elements are distinct.

Understanding the Problem

We need to determine the kth positive number that is missing from the sorted array.

Example

arr = [2, 3, 4, 7, 11]

The positive integers should ideally be:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...

Numbers missing from the array are:

1, 5, 6, 8, 9, 10, ...

Our goal is to find the kth number in this missing sequence.

Naive Approach

A straightforward solution would be:

Start from 1.
Check whether each number exists in the array.
Count missing numbers.
Stop when the kth missing number is found.

Complexity

O(n + k)

This becomes inefficient when k is very large.

Optimized Approach: Binary Search

Since the array is already sorted, we can use binary search.

The key is to determine how many numbers are missing before a particular index.

Step 1: Count Missing Numbers Before an Index

At index i, if no numbers were missing, we would expect:

arr[i] = i + 1

The actual value is larger because some numbers are missing.

Therefore:

missing(i) = arr[i] - (i + 1)

This gives the number of missing positive integers before arr[i].

Example

arr = [2, 3, 4, 7, 11]

At index 0:

missing(0) = 2 - 1 = 1

At index 3:

missing(3) = 7 - 4 = 3

At index 4:

missing(4) = 11 - 5 = 6

Why Binary Search Works

We want to find the first position where:

missing(i) ≥ k

Why?

Because the kth missing number must occur before that position.

This creates a monotonic property:

Smaller indices have fewer missing numbers.
Larger indices have more missing numbers.

That makes binary search applicable.

Binary Search Strategy

Maintain two pointers:

left = 0
right = n - 1

For each midpoint:

mid = left + (right - left) / 2

Compute:

missing = arr[mid] - (mid + 1)

Case 1: Missing Numbers Are Less Than k

If:

missing < k

the answer lies further right.

left = mid + 1

Case 2: Missing Numbers Are Greater Than or Equal to k

If:

missing ≥ k

the answer lies to the left.

right = mid - 1

Computing the Final Answer

After binary search completes:

left

represents the first position where:

missing(left) ≥ k

The kth missing number is:

left + k

Why Does left + k Work?

By the time we reach index left:

Exactly left array elements exist before that position.
We need to account for k missing numbers.

Combining both gives:

kth missing = left + k

Example Walkthrough

Input

arr = [2, 3, 4, 7, 11]
k = 5

Missing Counts

missing(0) = 1
missing(1) = 1
missing(2) = 1
missing(3) = 3
missing(4) = 6

We need:

missing(i) ≥ 5

The first such index is:

left = 4

Therefore:

kth missing = left + k
            = 4 + 5
            = 9

Answer

Java Implementation

class Solution {
    public int kthMissing(int[] arr, int k) {
        int n = arr.length;
        int left = 0, right = n - 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;
            }
        }

        // left is the position where missing(left) >= k
        return left + k;
    }
}

Complexity Analysis

Time Complexity

Binary search processes the array in:

O(log n)

Space Complexity

Only a few variables are used:

O(1)

Pattern Recognition

This problem belongs to the family of:

Binary Search on Answer
Missing Number Problems
Monotonic Search Space Problems

A common clue is when:

The array is sorted.
A counting function can be defined.
The count increases monotonically.

In such cases, binary search is often the optimal solution.

Key Takeaway

The crucial observation is that the number of missing elements before index i can be calculated as:

arr[i] - (i + 1)

This creates a monotonic sequence that allows binary search. Instead of generating missing numbers one by one, we locate the first index where the missing count reaches k and directly compute the answer in logarithmic time.

Summary

To find the kth missing positive number efficiently, calculate how many numbers are missing before each array index using arr[i] - (i + 1). Since this count increases monotonically, binary search can be used to find the first index where the missing count becomes at least k. The final answer is then computed as left + k, resulting in an optimal O(log n) time and O(1) space solution.