Code Implementation

class Solution:
    def missingElement(self, nums, k):
        def missing(idx):
            return nums[idx] - nums[0] - idx

        n = len(nums)
        if k > missing(n - 1):
            return nums[-1] + k - missing(n - 1)
        
        left, right = 0, n - 1
        while left < right:
            mid = (left + right) // 2
            if missing(mid) < k:
                left = mid + 1
            else:
                right = mid
        return nums[left - 1] + k - missing(left - 1)
      

class Solution {
public:
    int missingElement(vector<int>& nums, int k) {
        auto missing = [&nums](int idx) {
            return nums[idx] - nums[0] - idx;
        };
        int n = nums.size();
        if (k > missing(n - 1))
            return nums[n - 1] + k - missing(n - 1);
        int left = 0, right = n - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (missing(mid) < k)
                left = mid + 1;
            else
                right = mid;
        }
        return nums[left - 1] + k - missing(left - 1);
    }
};
      

class Solution {
    public int missingElement(int[] nums, int k) {
        int n = nums.length;
        int missing = nums[n - 1] - nums[0] - (n - 1);
        if (k > missing)
            return nums[n - 1] + k - missing;
        int left = 0, right = n - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            int miss = nums[mid] - nums[0] - mid;
            if (miss < k)
                left = mid + 1;
            else
                right = mid;
        }
        int missLeft = nums[left - 1] - nums[0] - (left - 1);
        return nums[left - 1] + k - missLeft;
    }
}
      

var missingElement = function(nums, k) {
    function missing(idx) {
        return nums[idx] - nums[0] - idx;
    }
    let n = nums.length;
    if (k > missing(n - 1))
        return nums[n - 1] + k - missing(n - 1);
    let left = 0, right = n - 1;
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        if (missing(mid) < k)
            left = mid + 1;
        else
            right = mid;
    }
    return nums[left - 1] + k - missing(left - 1);
};
      

Problem Description

Given a sorted array of unique integers nums and an integer k, find the k-th missing number starting from the first element of nums. The array is strictly increasing, and all elements are unique.

• You must return the actual value of the k-th missing number.
• There is exactly one valid answer for each input.
• Each element in nums can be used only once; do not reuse elements.
• The array may have missing numbers between elements, and may not start from 1.

Example:
If nums = [4,7,9,10], and k = 3, the missing numbers are 5, 6, 8. The 3rd missing number is 8.

Thought Process

The first idea is to enumerate all numbers between nums[0] and nums[-1], counting which are missing. For each gap between consecutive elements, we can count how many numbers are skipped. However, this brute-force approach can be slow if the numbers are large or the array is long.

To optimize, notice that the number of missing elements up to index i is nums[i] - nums[0] - i. This counts how many numbers are "skipped" from the start up to nums[i]. Using this, we can efficiently find where the k-th missing number falls, and even use binary search to speed it up.

If k is larger than the total number of missing numbers within the array, the answer must be after the last element. Otherwise, we can pinpoint the "gap" where the k-th missing occurs.

Solution Approach

• Step 1: Define a function missing(idx) that returns the number of missing numbers up to index idx: nums[idx] - nums[0] - idx.
• Step 2: Check if k is greater than the total number of missing numbers in the array (i.e., missing(n-1)). If so, the answer is past the last element: nums[-1] + k - missing(n-1).
• Step 3: If not, use binary search to find the smallest index left where missing(left) >= k. This means the k-th missing number lies just before nums[left].
• Step 4: The answer is nums[left-1] + k - missing(left-1), which shifts forward from the last known number by the remaining missing count needed to reach k.
• Why this works: Binary search lets us efficiently locate the correct "gap" in O(log n) time, and the missing() function quickly tells us how many numbers are missing up to any index.

Example Walkthrough

Example:
nums = [4,7,9,10], k = 3

1. Calculate missing numbers at each index:
   • missing(0) = 4-4-0 = 0
   • missing(1) = 7-4-1 = 2
   • missing(2) = 9-4-2 = 3
   • missing(3) = 10-4-3 = 3
2. The total missing up to the end is 3. Since k=3 is not greater than this, we use binary search:
   • left=0, right=3
   • mid=1: missing(1)=2 < 3, so left=2
   • mid=2: missing(2)=3 >= 3, so right=2
   • Loop ends when left=2
3. The answer is nums[1] + k - missing(1) = 7 + 3 - 2 = 8
4. Result: The 3rd missing number is 8.

Time and Space Complexity

• Brute-force approach: Iterating through all numbers between nums[0] and nums[-1] takes O(N + D) time, where D is the difference between first and last element. This can be slow for large gaps.
• Optimized approach: The binary search runs in O(log N) time, where N is the length of the array. Calculating missing(idx) is O(1).
• Space Complexity: Both approaches use O(1) extra space, as all calculations are done in-place.

Summary

The key insight is to use the formula nums[i] - nums[0] - i to quickly count missing numbers up to any index. By combining this with binary search, we efficiently find where the k-th missing number falls, even for large arrays and big gaps. This approach is both elegant and optimal, reducing time from linear to logarithmic while using constant space.