Prerequisites
Before attempting this problem, you should be comfortable with:
- Binary Search - The optimal solution uses binary search to find the position containing the k-th missing number in logarithmic time
- Sorted Array Properties - Understanding how to calculate missing elements between consecutive values in a sorted sequence
1. Iteration
Intuition
Since the array is sorted and strictly increasing, any missing numbers must fall in the gaps between consecutive elements. For each pair of adjacent elements, we can calculate how many numbers are missing by looking at the difference minus one. As we scan through the array, we count missing numbers until we accumulate at least k of them. Once we find the gap that contains the k-th missing number, we can compute its exact value.
Algorithm
- Iterate through the array from index
1ton - 1. - For each pair of consecutive elements, calculate
missedInGap = nums[i] - nums[i - 1] - 1. - If
missedInGap >= k, thek-th missing number lies in this gap. Returnnums[i - 1] + k. - Otherwise, subtract
missedInGapfromkand continue. - If we finish the loop without finding the answer, the
k-th missing number is beyond the last element. Returnnums[n - 1] + k.
Time & Space Complexity
- Time complexity:
- Space complexity: constant space
Where is the length of the input array
nums.
2. Binary Search
Intuition
Instead of scanning linearly, we can use binary search to find the position where the k-th missing number falls. The key observation is that for any index i, the count of missing numbers up to that point equals nums[i] - nums[0] - i. This formula works because in a complete sequence starting from nums[0], we would expect nums[0] + i at index i. The difference tells us how many numbers were skipped. Since this count is monotonically increasing, binary search applies naturally.
Algorithm
- Initialize
left = 0andright = n - 1. - While
left < right:- Calculate
midusing upper mid to avoid infinite loops. - Compute the number of missing elements up to index
mid:missing = nums[mid] - nums[0] - mid. - If
missing < k, thek-th missing number is to the right, so setleft = mid. - Otherwise, set
right = mid - 1.
- Calculate
- After the loop,
leftpoints to the largest index where the count of missing numbers is less thank. - Return
nums[0] + k + left.
class Solution:
def missingElement(self, nums: List[int], k: int) -> int:
n = len(nums)
left, right = 0, n - 1
while left < right:
mid = right - (right - left) // 2
if (nums[mid] - nums[0]) - mid < k:
left = mid
else:
right = mid - 1
return nums[0] + k + leftTime & Space Complexity
- Time complexity:
- Space complexity: constant space
Where is the length of the input array
nums.
Common Pitfalls
Miscounting Missing Elements
The formula for counting missing elements up to index i is nums[i] - nums[0] - i. Using nums[i] - i without subtracting nums[0] gives incorrect counts when the array does not start at 0 or 1.
Handling the Missing Element Beyond the Array
When k exceeds the total count of missing elements within the array, the answer lies beyond the last element. Failing to account for this case and only searching within array bounds leads to incorrect results or out-of-bounds errors.
Binary Search Boundary Errors
Using the wrong mid calculation or boundary updates can cause infinite loops or skip valid positions. The upper-mid formula mid = right - (right - left) / 2 is used here to avoid getting stuck; using standard lower-mid without proper boundary handling leads to incorrect convergence.