We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Missing Element in Sorted Array

Number: 1059

Difficulty: Medium

Paid? Yes

Companies: Meta, Arista Networks, Amazon

Problem Description

Given a sorted array of unique integers and an integer k, the task is to return the kth missing number in the sequence, counting from the leftmost element in the array.

Key Insights

  • The array is sorted and every element is unique.
  • For any index i, the number of missing numbers up to that point can be computed as nums[i] - nums[0] - i.
  • When missing(i) is less than k, the kth missing element is further to the right.
  • Use binary search to find the smallest index where the count of missing numbers is greater than or equal to k.
  • If all missing numbers before the last array element are counted and the kth missing still hasn't been reached, calculate the result by continuing past the last element.

Space and Time Complexity

Time Complexity: O(log(n)) Space Complexity: O(1)

Solution

We compute the number of missing elements until an index i with the formula: missing(i) = nums[i] - nums[0] - i. We then use binary search over the indices to find the smallest index where missing(i) >= k. If the binary search index equals the length of the array, it means the kth missing number lies beyond the last element. Otherwise, the kth missing number is derived as: nums[index - 1] + (k - missing(index - 1)). This approach uses binary search for logarithmic time and does not require extra auxiliary data structures.

Code Solutions

# Python solution with comprehensive comments

def missingElement(nums, k):
    # Calculate the missing count until index i: missing(i) = nums[i] - nums[0] - i.
    def missing_count(index):
        return nums[index] - nums[0] - index

    n = len(nums)
    
    # If kth missing number is beyond the last element.
    if k > missing_count(n - 1):
        return nums[-1] + k - missing_count(n - 1)

    # Perform binary search to find the smallest index where missing_count(index) >= k.
    left, right = 0, n - 1
    while left < right:
        mid = left + (right - left) // 2
        if missing_count(mid) < k:
            left = mid + 1
        else:
            right = mid

    # After binary search, left is the smallest index such that missing_count(left) >= k.
    # The kth missing number is after nums[left - 1].
    return nums[left - 1] + k - missing_count(left - 1)

# Example usage:
print(missingElement([4,7,9,10], 3))  # Output: 8
← Back to All Questions