Is Missing Element in Sorted Array easy or hard?

The problem is rated Medium difficulty. The challenge is recognizing that the number of missing values forms a monotonic sequence, which allows binary search instead of scanning every gap.

Missing Element in Sorted Array Python/Java solution

Implement the binary search method by computing missing(i) = nums[i] - nums[0] - i and adjusting search boundaries until the first index with missing(i) >= k is found. The final answer is derived from the previous element and remaining k. The same logic works in Python, Java, C++, and Go.

How to solve Missing Element in Sorted Array in O(log n)?

Use binary search on the number of missing elements up to each index. Calculate missing(i) = nums[i] - nums[0] - i. If missing(mid) is smaller than k, move right; otherwise move left. After locating the boundary index, compute the result using nums[i-1] + (k - missing(i-1)).

What is the best approach for Missing Element in Sorted Array?

Binary search with a missing-count formula is the best approach. Compute missing numbers up to index i using nums[i] - nums[0] - i, which forms a monotonic function across the sorted array. Binary search locates the first index where the missing count reaches k, giving an O(log n) time and O(1) space solution.

Is Missing Element in Sorted Array asked at Google/Amazon/Meta?

Missing Element in Sorted Array appears in interview preparation sets for companies like Google and Amazon because it tests binary search reasoning on a monotonic function. The problem checks whether you can transform a counting problem into a searchable condition.

What data structure is used in Missing Element in Sorted Array?

The problem primarily uses arrays and binary search. The array remains sorted, allowing you to derive a mathematical formula for the number of missing elements and search efficiently without extra data structures.

What is the time complexity of Missing Element in Sorted Array?

The optimal solution runs in O(log n) time using binary search on the missing-count function. A simpler linear scan approach runs in O(n) time by checking gaps between adjacent elements. Both approaches use O(1) extra space.

Description Hints 2 Solution Video 11:18

1060. Missing Element in Sorted Array

Medium59.7% acceptance4 companiesPremium elsewhere, free here

Given an integer array nums which is sorted in ascending order and all of its elements are unique and given also an integer k, return the k^th missing number starting from the leftmost number of the array.

Example 1:

Input: nums = [4,7,9,10], k = 1
Output: 5
Explanation: The first missing number is 5.

Example 2:

Input: nums = [4,7,9,10], k = 3
Output: 8
Explanation: The missing numbers are [5,6,8,...], hence the third missing number is 8.

Example 3:

Input: nums = [1,2,4], k = 3
Output: 6
Explanation: The missing numbers are [3,5,6,7,...], hence the third missing number is 6.

Constraints:

1 <= nums.length <= 5 * 10⁴
1 <= nums[i] <= 10⁷
nums is sorted in ascending order, and all the elements are unique.
1 <= k <= 10⁸

Follow up: Can you find a logarithmic time complexity (i.e., O(log(n))) solution?

Asked at 4 companies

Meta PayPal Amazon

Google

Topics

Array Binary Search

Hints open one at a time

Hint 1

First define a function f(x) that counts the number of missing elements until x.

Hint 2

Then use binary search with the given function f(x) to find the kth missing element.

11:18

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[4,7,9,10]
1

Input

[4,7,9,10]
3

Input

[1,2,4]
3

Your code is saved on this device.Solution