Problem Description

You are given an integer array nums that is sorted in ascending order, where all elements are unique. You're also given an integer k.

The task is to find the kth missing number in the sequence, starting from the leftmost (first) element of the array.

A "missing number" is any integer that should appear in the continuous sequence starting from nums[0] but is not present in the array. For example:

• If nums = [4, 7, 9, 10] and k = 1, the first missing number starting from 4 would be 5 (since 5 is not in the array).
• If k = 2, the second missing number would be 6.
• If k = 3, the third missing number would be 8.

The solution uses binary search to efficiently find the kth missing number. The helper function missing(i) calculates how many numbers are missing up to index i by using the formula: nums[i] - nums[0] - i. This works because in a continuous sequence with no missing numbers, the element at index i would be nums[0] + i.

The algorithm first checks if k is greater than the total number of missing elements in the array range. If so, it calculates the answer by extending beyond the last element. Otherwise, it uses binary search to find the position where exactly k missing numbers have occurred, then calculates the kth missing number based on that position.

Intuition

The key insight is recognizing that we can calculate how many numbers are missing up to any position in the array without actually listing them out.

Think about it this way: if we have a perfectly continuous sequence starting from nums[0], the element at index i should be nums[0] + i. For example, if nums[0] = 4, then ideally we'd have [4, 5, 6, 7, ...]. But in reality, we might have [4, 7, 9, ...] where some numbers are skipped.

The difference between what we actually have (nums[i]) and what we should have (nums[0] + i) tells us exactly how many numbers are missing up to that point. This gives us the formula: missing(i) = nums[i] - nums[0] - i.

Once we can efficiently count missing numbers at any position, finding the kth missing number becomes a search problem. We need to find where in the array the count of missing numbers transitions from less than k to at least k.

Since the array is sorted and the count of missing numbers is monotonically increasing (we can only have more missing numbers as we go further, never fewer), we can use binary search. We're essentially searching for the leftmost position where we have at least k missing numbers.

The edge case is when k is larger than all the missing numbers within the array range. In this case, the kth missing number must be beyond the last element of the array, and we can calculate it directly by extending from the last element.

Learn more about Binary Search patterns.

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 Implementation:

   • Initialize pointers: l = 0, r = n - 1
   • Search for the leftmost position where missing(mid) >= k
   • In each iteration:
     • Calculate mid = (l + r) >> 1 (bit shift for division by 2)
     • If missing(mid) >= k: move right pointer to mid
     • Otherwise: move left pointer to mid + 1

3. Calculate the Result:

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

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 Looking for the leftmost position where missing(mid) >= k:

Iteration 1:

• l = 0, r = 3
• mid = (0 + 3) >> 1 = 1
• missing(1) = 2, which is less than k = 3
• Move left pointer: l = 2

Iteration 2:

• l = 2, r = 3
• mid = (2 + 3) >> 1 = 2
• missing(2) = 3, which equals k = 3
• Move right pointer: r = 2

Iteration 3:

• l = 2, r = 2, loop ends

Step 4: Calculate the result

• l = 2, so we look at position l - 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.

Solution Implementation

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. Off-by-One Error in Binary Search Boundary

A frequent mistake is incorrectly handling the binary search boundaries, particularly when determining whether to include mid in the next search range.

Pitfall Example:

# Incorrect: Using left = mid instead of left = mid + 1
while left < right:
    mid = (left + right) // 2
    if count_missing_before_index(mid) >= k:
        right = mid
    else:
        left = mid  # Wrong! Can cause infinite loop

Why it fails: When left and right differ by 1, mid equals left, and if the condition fails, left never advances, causing an infinite loop.

Solution: Always use left = mid + 1 when the condition fails to ensure progression.

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.