Solution Approach

The solution implements a binary search algorithm with a helper function to efficiently find the kth missing number.

Helper Function: The missing(i) function calculates the count of missing numbers up to index i:

• Formula: nums[i] - nums[0] - i
• This represents the difference between the actual value at index i and what it should be in a continuous sequence

Main Algorithm Steps:

1. Check if k exceeds array bounds:

   • Calculate total missing numbers in the array: missing(n - 1)
   • If k > missing(n - 1), the answer lies beyond the array
   • Return: nums[n - 1] + k - missing(n - 1)
   • This adds the remaining missing numbers to the last element

2. Binary Search Using the Template:

   • Feasible condition: missing(mid) >= k - does this index have at least k missing numbers before it?
   • This creates a pattern: [false, false, ..., true, true, true]
   • We want to find the first true index
   • Initialize: left = 0, right = n - 1, first_true_index = -1
   • Loop while left <= right:
     • Calculate mid = (left + right) // 2
     • If missing(mid) >= k (feasible): record first_true_index = mid, then search left with right = mid - 1
     • Otherwise: search right with left = mid + 1

3. Calculate the Result:

   • After binary search, first_true_index is the first index where we have at least k missing numbers
   • The kth missing number is between indices first_true_index - 1 and first_true_index
   • Return: nums[first_true_index - 1] + k - missing(first_true_index - 1)
   • This formula adds the remaining missing numbers needed to reach k from the previous position

Time Complexity: O(log n) due to binary search Space Complexity: O(1) as we only use a few variables

The elegance of this solution lies in avoiding the enumeration of all missing numbers and instead using mathematical relationships to directly compute the answer.

Example Walkthrough

Let's walk through the solution with nums = [4, 7, 9, 10] and k = 3.

Step 1: Calculate missing numbers at each index Using the formula missing(i) = nums[i] - nums[0] - i:

• Index 0: missing(0) = 4 - 4 - 0 = 0 (no missing numbers before 4)
• Index 1: missing(1) = 7 - 4 - 1 = 2 (numbers 5 and 6 are missing)
• Index 2: missing(2) = 9 - 4 - 2 = 3 (numbers 5, 6, and 8 are missing)
• Index 3: missing(3) = 10 - 4 - 3 = 3 (same 3 missing numbers)

Step 2: Check if k exceeds array bounds

• Total missing in array: missing(3) = 3
• Since k = 3 is not greater than 3, we proceed with binary search

Step 3: Binary Search Using Template

• Feasible condition: missing(mid) >= k
• Initialize: left = 0, right = 3, first_true_index = -1

Iteration 1:

• left = 0, right = 3
• mid = (0 + 3) // 2 = 1
• missing(1) = 2 < k = 3 → NOT feasible
• Move left pointer: left = 2

Iteration 2:

• left = 2, right = 3
• mid = (2 + 3) // 2 = 2
• missing(2) = 3 >= k = 3 → Feasible!
• Record: first_true_index = 2
• Move right pointer: right = 1

Iteration 3:

• left = 2, right = 1
• left > right, loop ends

Step 4: Calculate the result

• first_true_index = 2, so we look at position first_true_index - 1 = 1
• missing(1) = 2 (we have 2 missing numbers by index 1)
• We need k - missing(1) = 3 - 2 = 1 more missing number
• Result: nums[1] + (k - missing(1)) = 7 + 1 = 8

Verification: The missing numbers in order are: 5, 6, 8. The 3rd missing number is indeed 8.

Time and Space Complexity

Time Complexity: O(log n)

The algorithm uses binary search to find the position where the k-th missing element would be. The missing(i) helper function calculates how many numbers are missing up to index i in constant time O(1). The binary search loop runs for O(log n) iterations where n is the length of the input array. Each iteration performs constant time operations including calling missing(), comparisons, and index calculations. Therefore, the overall time complexity is O(log n).

Space Complexity: O(1)

The algorithm uses only a constant amount of extra space. The variables l, r, mid, and n are all integers that occupy constant space. The helper function missing(i) doesn't create any additional data structures and only performs arithmetic operations. No recursive calls are made, so there's no additional stack space usage beyond the function call itself. Therefore, the space complexity is O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Using the Wrong Binary Search Template

A common mistake is using while left < right with right = mid instead of the standard template with while left <= right and first_true_index tracking.

Pitfall Example:

# Incorrect: Using alternative template
while left < right:
    mid = (left + right) // 2
    if count_missing_before_index(mid) >= k:
        right = mid
    else:
        left = mid + 1
return nums[left - 1] + k - count_missing_before_index(left - 1)

Why it's problematic: This variant works but differs from the standard template pattern. The standard template explicitly tracks the answer with first_true_index, making the logic clearer.

Solution: Use the standard template with while left <= right and first_true_index:

first_true_index = -1
while left <= right:
    mid = (left + right) // 2
    if count_missing_before_index(mid) >= k:
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1

2. Incorrect Final Calculation Formula

Another common error is using the wrong index or formula when calculating the final result.

Pitfall Example:

# Incorrect: Using nums[left] instead of nums[left - 1]
return nums[left] + k - count_missing_before_index(left)

Why it fails: After binary search, left points to the first position where we have at least k missing numbers. The k-th missing number lies between nums[left-1] and nums[left], not after nums[left].

Solution: Use nums[left - 1] + k - count_missing_before_index(left - 1) to correctly calculate from the previous position.

3. Not Handling Edge Case When k=1 and left=0

When the first missing number occurs before the first element, accessing nums[left - 1] causes an index error.

Pitfall Example:

# If nums = [5, 7, 9] and k = 1, the first missing is before index 0
# After binary search, left = 0
return nums[left - 1] + k - count_missing_before_index(left - 1)  # IndexError!

Solution: Add a special check for when left == 0:

if left == 0:
    # All k missing numbers come before the first element
    return nums[0] - k
else:
    return nums[left - 1] + k - count_missing_before_index(left - 1)

4. Misunderstanding the Missing Count Formula

Developers sometimes incorrectly calculate the missing count by forgetting to subtract the starting position.

Pitfall Example:

# Incorrect: Not accounting for the starting position
def count_missing_before_index(index):
    return nums[index] - index  # Wrong! Assumes sequence starts at 0

Why it fails: If nums = [4, 7, 9], this would incorrectly calculate missing(0) = 4, when actually no numbers are missing before index 0 (since we start counting from 4).

Solution: Always use nums[index] - nums[0] - index to correctly count missing numbers relative to the starting element.