Given an integer array nums which is sorted in ascending order and all of its elements are unique and given also an integer k, return the kth missing number starting from the leftmost number of the array.
Example 1:
Input: nums = [4,7,9,10], k = 1 Output: 5 Explanation: The first missing number is 5.
Example 2:
Input: nums = [4,7,9,10], k = 3 Output: 8 Explanation: The missing numbers are [5,6,8,...], hence the third missing number is 8.
Example 3:
Input: nums = [1,2,4], k = 3 Output: 6 Explanation: The missing numbers are [3,5,6,7,...], hence the third missing number is 6.
Constraints:
1 <= nums.length <= 5 * 1041 <= nums[i] <= 107nums is sorted in ascending order, and all the elements are unique.1 <= k <= 108Follow up: Can you find a logarithmic time complexity (i.e.,
O(log(n))) solution?Problem Overview: You get a strictly increasing sorted array and an integer k. Some numbers are missing from the natural sequence. Your job is to return the k-th missing number relative to the array.
Approach 1: Linear Scan with Missing Count (O(n) time, O(1) space)
Traverse the array and count how many numbers are missing between adjacent elements. The gap between nums[i] and nums[i-1] equals nums[i] - nums[i-1] - 1. Subtract that gap from k as you move forward. When k falls inside a gap, the answer is nums[i-1] + k. If the loop finishes and k is still positive, the missing element lies after the last value, so return nums[n-1] + k. This approach is straightforward and works well for smaller inputs, but it scans the array sequentially.
Approach 2: Binary Search Using Missing Index Formula (O(log n) time, O(1) space)
The sorted property enables a faster solution with binary search. Instead of counting gaps one by one, compute how many numbers are missing up to index i. The formula is missing(i) = nums[i] - nums[0] - i. It measures the difference between the expected value in a perfect sequence and the actual value in the array. If missing(mid) < k, the k-th missing number lies to the right; otherwise it lies to the left.
Once binary search finds the first index where the missing count becomes at least k, the answer lies between two array elements. Let the previous index be i - 1. You already know how many numbers were missing before that point, so compute the final value as nums[i-1] + (k - missing(i-1)). This avoids scanning every gap and jumps directly to the region containing the answer.
This method works because the missing-count function grows monotonically across the sorted array. Binary search exploits that monotonic behavior to narrow the search space from n elements down to log n comparisons.
Recommended for interviews: The binary search approach. Interviewers expect you to notice the sorted structure and derive the missing(i) formula. Starting with the linear scan demonstrates clear reasoning about gaps, but the optimized binary search shows stronger algorithmic thinking and familiarity with search patterns on monotonic functions.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Linear Scan with Gap Counting | O(n) | O(1) | Good for quickly implementing the idea or when the array is small |
| Binary Search with Missing Count Formula | O(log n) | O(1) | Best choice for interviews and large arrays since the input is sorted |
Leetcode 1060 Missing Element in Sorted Array • Ren Zhang • 6,590 views views
Watch 9 more video solutions →Practice Missing Element in Sorted Array with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor