Missing Element In Sorted Array - Leetcode Solution

Problem Statement:

You are given a sorted array that is missing one element. Your task is to find and return that missing element.

Example 1:

Input: [4,7,9,10]

Output: 8

Explanation: The missing element in the array is 8.

Example 2:

Input: [1,2,4,5,6]

Output: 3

Explanation: The missing element in the array is 3.

Approach:

We can solve this problem by using binary search. We select a middle element and check whether it is at its expected position or not. If it is at the expected position, then we know that the missing element is on the right side of the array. Otherwise, the missing element is on the left side of the array. We keep applying this logic until we find the missing element.

Algorithm:

1. Initialize two pointers, left and right, at the start and end of the array.
2. While the left pointer is less than or equal to the right pointer: a. Calculate the middle index using the formula (left + right) / 2. b. Check whether the middle element is at its expected position or not. If it is, then move the left pointer to the middle index + 1. If it is not, then move the right pointer to the middle index - 1.
3. The missing element is the element at the left pointer.

Code:

Here is the Python implementation of the above algorithm.

class Solution: def missingElement(self, nums: List[int], k: int) -> int: left, right = 0, len(nums) - 1

    # check the number of missing elements before the first element
    if nums[0] + k - 1 < nums[left]:
        return nums[0] + k - 1
    
    while left <= right:
        mid = (left + right) // 2
        # check the number of missing elements before the middle element
        missing = nums[mid] - nums[0] - mid
        if missing < k:
            # move the left pointer to the right of the middle element
            left = mid + 1
        else:
            # move the right pointer to the left of the middle element
            right = mid - 1
    
    # the missing element is between the left and right pointers
    return nums[left - 1] + k - (nums[left - 1] - nums[0] - (left - 1))

1