Binary Search - DSA: Kth Missing Positive Number

1. Problem Statement & Overview

Given an increasing array of positive integers and an integer $K$, our task is to find the $K$-th missing positive integer from the sequence starting at $1$.

• Input: A sorted array of positive integers (e.g., [2, 3, 4, 7, 11]) and an integer $K$ (e.g., $K = 5$).
• Output: The $K$-th missing positive number (e.g., for the example above, the missing numbers are 1, 5, 6, 8, 9, 10, ..., and the $5$-th missing number is 9).

2. Real-Life Mental Model & Analogy

The Hostel Room Assignment Analogy

Imagine a row of hostel rooms numbered sequentially starting from $1$:

Room Numbers: [ 1 ]  [ 2 ]  [ 3 ]  [ 4 ]  [ 5 ]  [ 6 ]  [ 7 ]  [ 8 ]  [ 9 ]  [ 10 ]  [ 11 ]
Occupancy:      X    Occup. Occup. Occup.   X      X    Occup.   X      X       X     Occup.

• Some rooms are occupied (represented by the numbers present in our array).
• Other rooms are vacant (missing numbers).
• If you are asked to walk down the hallway and find the $5$-th vacant room, you count the empty doors one by one until you hit your target.
• The Brute Force approach physically walks through every single room. The Binary Search approach skips blocks of rooms by checking how many vacancies have accumulated up to a certain point.

3. Naive Approach: The Brute Force Strategy

How It Works

We can iterate through natural numbers starting from $1$ or iterate through the array while keeping track of how many numbers are missing relative to our target $K$.

Alternatively, as demonstrated in the lecture, we check each element in the array: if the array element is less than or equal to $K$, it means this number occupies a spot that would otherwise be a missing candidate. Therefore, we increment $K$ to shift our target forward.

Brute Force Code Implementation (C++)

int findKthPositive(vector<int>& arr, int k) {
    for (int i = 0; i < arr.size(); i++) {
        if (arr[i] <= k) {
            k++; // This element takes up a slot, so our target shifts forward
        } else {
            break; // We have exceeded our target threshold
        }
    }
    return k;
}

Complexity Analysis

• Time Complexity: $O(N)$ where $N$ is the number of elements in the array.
• Space Complexity: $O(1)$ auxiliary space.

4. Why We Need Binary Search & Intuition Breakdown

When an array is sorted and increasing, and we need a performance upgrade from $O(N)$, Binary Search is the natural choice.

However, two classic binary search techniques fail here:

1. Standard Binary Search: Fails because the target number is not present in the array.
2. Binary Search on Answers: Typically used for optimization problems with monotonic ranges (minimum/maximum bounds), which doesn't directly map here since we are searching for an index bracket where the missing count transitions past $K$.

The Core Insight: Counting Missing Numbers

At any index mid, how many numbers are missing strictly before or at arr[mid]?

• Ideal Value at Index: In a pristine, uninterrupted sequence starting at $1$, the value at index mid should be mid + 1 (assuming 0-based indexing).
• Actual Value at Index: arr[mid].
• Formula for Missing Numbers:

Let's test this formula on arr = [2, 3, 4, 7, 11] with $K = 5$:

• At index 0 (val 2): missing = $2 - (0 + 1) = 1$
• At index 1 (val 3): missing = $3 - (1 + 1) = 1$
• At index 2 (val 4): missing = $4 - (2 + 1) = 1$
• At index 3 (val 7): missing = $7 - (3 + 1) = 3$
• At index 4 (val 11): missing = $11 - (4 + 1) = 6$

We are looking for $K = 5$. Notice that the missing count transitions from $3$ (at index $3$) to $6$ (at index $4$). Therefore, our answer lies between index $3$ and index $4$ (or more specifically, right after high pointer settles).

5. Step-by-Step Binary Search Evolution

We set up our search space:

• low = 0
• high = n - 1

   Low (0)                      High (n-1)
      |                             |
[ 2,  3,  4,  7,  11 ]   (K = 5)

Execution Trace:

1. Iteration 1: mid = (0 + 4) / 2 = 2.
   • arr[2] = 4. Missing = $4 - (2 + 1) = 1$.
   • Since missing ($1$) $< K$ ($5$), our target is further right. Eliminate left half: low = mid + 1 ($3$).
2. Iteration 2: mid = (3 + 4) / 2 = 3.
   • arr[3] = 7. Missing = $7 - (3 + 1) = 3$.
   • Since missing ($3$) $< K$ ($5$), eliminate left half: low = mid + 1 ($4$).
3. Iteration 3: mid = (4 + 4) / 2 = 4.
   • arr[4] = 11. Missing = $11 - (4 + 1) = 6$.
   • Since missing ($6$) $\ge K$ ($5$), eliminate right half: high = mid - 1 ($3$).

At the end of the loop, low points to index $4$ (value $11$) and high points to index $3$ (value $7$). Notice the opposite polarity:

• high stopped where missing count $< K$ ($3$).
• low stopped where missing count $\ge K$ ($6$).

6. Deriving the O(1) Mathematical Formula for the Answer

When binary search terminates, high and low cross paths (low = high + 1). How do we compute the exact $K$-th missing number without relying directly on arr[high] (which might be out of bounds if high drops to -1)?

Derivation Steps:

1. We know the number of missing elements up to high is:

2. How many more missing numbers do we need beyond what high has already accounted for?

3. Our final answer is the value at high plus these extra numbers needed:

Since low = high + 1, this simplifies beautifully to:

This explains why returning low + K works universally, even when high falls off to -1 (e.g., when the array starts with numbers larger than $K$).

7. Complete Optimized Code Implementation

Here is the clean, production-ready implementation of the algorithm:

#include <vector>
using namespace std;

class Solution {
public:
    int findKthPositive(vector<int>& arr, int k) {
        int low = 0, high = arr.size() - 1;
        
        while (low <= high) {
            int mid = low + (high - low) / 2;
            
            // Calculate missing numbers up to index 'mid'
            int missing = arr[mid] - (mid + 1);
            
            if (missing < k) {
                low = mid + 1; // Look to the right half
            } else {
                high = mid - 1; // Look to the left half
            }
        }
        
        // Alternatively, return high + 1 + k;
        return low + k;
    }
};

8. Summary and Key Takeaways

• Problem Nature: Finding the $K$-th missing positive number in a sorted increasing array requires tracking the count of missing integers relative to ideal indices.
• Sub-optimal vs. Optimal: Brute force scans elements in $O(N)$ time, whereas Binary Search cuts the search space down to logarithmic time $O(\log N)$.
• Missing Count Formula: At any index mid, the number of missing integers is given by $\text{arr[mid]} - (\text{mid} + 1)$.
• Binary Search Invariant: We use binary search to find the exact boundary where the missing count transitions from less than $K$ to greater than or equal to $K$.
• Pointer Cross-Over: When the loop terminates, high and low cross over, establishing a precise interpolation bracket.
• The Elegant Result Formula: By algebraic reduction, the final answer simplifies cleanly to $\text{low} + K$ (or $\text{high} + 1 + K$), avoiding edge-case index out-of-bounds errors.
• Space Efficiency: The solution operates with $O(1)$ auxiliary space complexity.