1060. Missing Element in Sorted Array

/**

 * 1060. Missing Element in Sorted Array

 * Given a sorted array A of unique numbers, find the K-th missing number starting from the leftmost number of the array.

 * Example 1:

 *

 * Input: A = [4,7,9,10], K = 1

 * Output: 5

 * Explanation:

 * The first missing number is 5.

*/

See solution to this problem on github here: https://github.com/zcoderz/leetcode/blob/main/src/main/java/search/binary_search/MissingElements.java

Observation: The array is sorted and we are asked to find the kth missing element. Missing element occurs when nums[index] – nums[0] > index + nums[0]. And the number of missing element between left and right indexes can be found by: nums[right]  – nums[left] – (right – left). Thus, given the array is sorted we can use binary search to find the kth missing element.

If the number of the missing element being requested is greater than the number of missing elements existing in the array then we simply return the last element in array + (k – gaps-existing-in-array).

In the binary search, we move left off of the mid if left has enough missing elements. Otherwise, we move right while subtracting the number of missing elements that were left off of the mid.

When left and right converge, meaning that distance between left and right is 1, then the kth missing element must be nums[left] + k since by definition we will enter this condition only if enough missing elements existed in this range.

Here is the main driver method:

public int missingElement(int[] nums, int k) {
    if (nums.length == 0) return k;
    int gaps = (nums[nums.length - 1] - nums[0]) - (nums.length) + 1;
    if (k > gaps) {
        //if more gaps requested than the number that occur in array
        //get the kth missing via the below equation
        return nums[nums.length - 1] + (k - gaps);
    }
    //do a binary search
    return search(nums, 0, nums.length - 1, k);
}

Here is the code performing the binary search:

int search(int[] nums, int left, int right, int k) {
    if ((right - left) == 1) {
        //the offset between left and right is 1 but there may be any k numbers left
        //hence break here and add the remaining k to nums[left]
        return nums[left] + k;
    }
    int mid = (left + right) / 2;
    //find the gap between left and mid
    int theGap = ((nums[mid] - nums[left]) - (mid - left));
    if (theGap >= k) {
        //left off of mid has enough missing, so focus on left
        return search(nums, left, mid, k);
    } else {
        //left of mid didn't have enough missing , so find the remaining missing on the right
        int gaps = k - theGap;
        return search(nums, mid, right, gaps);
    }
}