Brute Force Approach for Kth Missing Positive Number

A naive approach is to iterate through the array and count how many numbers are missing as we progress. Since the array is sorted, we can compare the current value arr[i] with the expected value if no numbers were missing (which would be i + 1).

Alternatively, we can iterate through all positive integers starting from 1. We check if the current integer exists in the array. If it does not, we decrement k. When k reaches 0, the current integer is our answer.

Naive Algorithm:

1. Initialize a pointer for the array and a counter for the current positive integer.
2. Loop while k > 0.
3. Check if the current integer matches the current array element.
4. If yes, move the array pointer.
5. If no, decrement k (we found a missing number).
6. Increment the current integer.
7. Return the integer that caused k to reach 0.

Time Complexity: $O(N + K)$. In the worst case, if $k$ is very large, we might iterate far beyond the array bounds. Why it fails: While this passes small constraints, the follow-up explicitly asks for a solution with less than $O(N)$ complexity. For very large $N$ or $K$, linear scanning is suboptimal compared to binary search.

Core Insight for Kth Missing Positive Number

The key to solving LeetCode 1539 in $O(\log N)$ time lies in calculating the number of missing integers directly from the array indices without linear scanning.

Consider an index i in the array arr. If there were no missing numbers, the value at arr[i] would be exactly i + 1 (since the array is 0-indexed and contains positive integers starting from 1). Therefore, the number of missing integers strictly before index i is: $\text{missing\_count} = \text{arr}[i] - (i + 1)$

Invariant: Since arr is strictly increasing integers, the value arr[i] - (i + 1) is non-decreasing.

• If arr[i] = x, then arr[i+1] must be at least x + 1.
• The missing count at i+1 is arr[i+1] - (i + 2).
• Substituting the minimum possible value: (x + 1) - (i + 2) = x - i - 1, which is the same as arr[i] - (i + 1).
• Thus, the gap (missing count) either stays the same or increases.

This monotonicity allows us to apply Binary Search. We want to find the smallest index where the number of missing integers is at least k. The answer will be located relative to the split point found by the binary search.

Visual Description: Imagine plotting arr[i] against the index i. The line y = i + 1 represents a complete sequence with no missing numbers. The actual values arr[i] form a curve strictly above or on this line. The vertical distance between arr[i] and i + 1 represents the cumulative count of missing numbers up to that point. We binary search this "distance" to find where it crosses the threshold k.

Execution Flow

Let's trace arr = [2, 3, 4, 7, 11] and k = 5.

1. Start: left = 0, right = 4.
2. Iteration 1:
   • mid = 2. arr[2] = 4.
   • missing = 4 - (2 + 1) = 1.
   • Since 1 < 5, we need more missing numbers.
   • left = mid + 1 = 3.
3. Iteration 2:
   • mid = 3. arr[3] = 7.
   • missing = 7 - (3 + 1) = 3.
   • Since 3 < 5, we need more missing numbers.
   • left = mid + 1 = 4.
4. Iteration 3:
   • mid = 4. arr[4] = 11.
   • missing = 11 - (4 + 1) = 6.
   • Since 6 >= 5, the target is to the left.
   • right = mid - 1 = 3.
5. Termination:
   • left (4) is now greater than right (3). Loop ends.
6. Calculation:
   • Result = left + k = 4 + 5 = 9.
   • Verification: Missing numbers are 1, 5, 6, 8, 9. The 5th is indeed 9.

Proof of Correctness

Why is the answer left + k?

At the end of the binary search, right is the largest index such that arr[right] - (right + 1) < k. The variable left is equal to right + 1. The number of missing integers strictly before arr[right] is missing_count = arr[right] - (right + 1). Since missing_count < k, the $k$-th missing number is located after arr[right]. Specifically, we need to find the $(k - \text{missing\_count})$-th missing number starting after arr[right].

Since there are no elements between arr[right] and the theoretical missing number we are looking for (because arr is sorted and we are looking in the gap), the numbers immediately following arr[right] are missing. The answer is: $\text{Answer} = \text{arr}[right] + (k - \text{missing\_count})$ Substitute missing_count: $\text{Answer} = \text{arr}[right] + k - (\text{arr}[right] - (right + 1))$ $\text{Answer} = \text{arr}[right] + k - \text{arr}[right] + right + 1$ $\text{Answer} = k + right + 1$ Since left = right + 1, the formula simplifies to: $\text{Answer} = k + left$

This derivation holds even for edge cases (e.g., when the missing number is before the first element or after the last).

Reference Implementation

C++ Solution for LeetCode 1539

cpp
class Solution {
public:
    int findKthPositive(vector<int>& arr, int k) {
        int left = 0;
        int right = arr.size() - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            // Calculate how many numbers are missing up to index mid
            int missing = arr[mid] - (mid + 1);

            if (missing < k) {
                // If missing count is less than k, the answer is to the right
                left = mid + 1;
            } else {
                // If missing count is >= k, the answer is to the left
                right = mid - 1;
            }
        }

        // The formula derived in the proof: k + left
        return left + k;
    }
};

Java Solution for LeetCode 1539

java
class Solution {
    public int findKthPositive(int[] arr, int k) {
        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            // Calculate how many numbers are missing up to index mid
            int missing = arr[mid] - (mid + 1);

            if (missing < k) {
                // We need more missing numbers, so look right
                left = mid + 1;
            } else {
                // We have enough missing numbers, so look left
                right = mid - 1;
            }
        }

        // Based on the derivation: answer = k + left
        return left + k;
    }
}

Python Solution for LeetCode 1539

python
class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        left, right = 0, len(arr) - 1
        
        while left <= right:
            mid = left + (right - left) // 2
            # Calculate missing count at index mid
            missing = arr[mid] - (mid + 1)
            
            if missing < k:
                # Not enough missing numbers yet, move right
                left = mid + 1
            else:
                # Enough or too many missing numbers, move left
                right = mid - 1
                
        # The result is derived as k + left
        return left + k

Q: Why do I get off-by-one errors?

Mistake: Using arr[mid] - mid instead of arr[mid] - (mid + 1). Why: Array indices are 0-based, but the positive integers start at 1. The expected value at index 0 is 1. Consequence: The calculated missing count is incorrect, leading to the wrong search direction and an incorrect result.

Q: Why return left + k instead of arr[left] + k?

Mistake: Trying to offset from the array value arr[left] rather than the index. Why: The logic arr[left] + something is complex because left might be out of bounds (equal to arr.length) after the loop. The formula left + k is mathematically derived to handle all cases, including when the answer lies outside the array bounds. Consequence: Runtime errors (IndexOutOfBounds) or incorrect logic for edge cases.