Missing Element in Sorted Array

Missing Element in Sorted Array

What is this problem about?

The Missing Element in Sorted Array problem gives you a sorted array of unique integers and asks for the k-th missing number starting from the first element of the array. Unlike standard "find missing number" problems, this one asks for the k-th missing value in an extended range. The Missing Element in Sorted Array coding problem tests binary search reasoning on sorted arrays with gaps.

Why is this asked in interviews?

PayPal, Meta, Amazon, and Google ask this because it tests binary search on a derived property — the number of missing integers before index i equals arr[i] - arr[0] - i. This non-trivial binary search setup differentiates candidates who can derive search conditions from those who only apply templates. The array and binary search interview pattern is the core here.

Algorithmic pattern used

Binary search on missing count. At each index i, the count of missing numbers before arr[i] is arr[i] - arr[0] - i. Binary search for the rightmost index where missing count < k. If found at index lo, the k-th missing number is arr[lo] + (k - missing_count_at_lo).

Example explanation

Array: [4, 7, 9, 10]. k = 3.

• Missing count at index 0: 0, index 1: 7-4-1=2, index 2: 9-4-2=3, index 3: 10-4-3=3.
• Find rightmost index where missing < 3: that's index 1 (missing=2).
• k-th missing = arr[1] + (3-2) = 7+1 = 8.

Common mistakes candidates make

• Linear scanning instead of binary searching (O(n) vs O(log n)).
• Incorrect formula for counting missing numbers (forgetting to subtract the index).
• Off-by-one in locating the final answer after binary search.
• Not handling the case where k exceeds all missing numbers within the array range.

Interview preparation tip

Derived-property binary search problems require you to define a monotonic function over the array. Here, "count of missing numbers before index i" is monotonically non-decreasing, making binary search valid. Practice deriving such functions from array properties before applying binary search — this is the skill that unlocks a whole class of medium-to-hard binary search problems at companies like Meta and Google.