Skip to main content
Talentd

Missing Element in Sorted Array - Solution & Explanation

MediumPremiumFree on FleetCodeArrayBinary Search5 min readAsked at: Amazon, Meta, PayPal +1
Practice this problem

Problem Statement

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 kth 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 * 104
  • 1 <= nums[i] <= 107
  • nums is sorted in ascending order, and all the elements are unique.
  • 1 <= k <= 108

 

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

Approach Overview

Problem Overview: You get a strictly increasing sorted array and an integer k. Some numbers are missing from the natural sequence. Your job is to return the k-th missing number relative to the array.

Approach 1: Linear Scan with Missing Count (O(n) time, O(1) space)

Traverse the array and count how many numbers are missing between adjacent elements. The gap between nums[i] and nums[i-1] equals nums[i] - nums[i-1] - 1. Subtract that gap from k as you move forward. When k falls inside a gap, the answer is nums[i-1] + k. If the loop finishes and k is still positive, the missing element lies after the last value, so return nums[n-1] + k. This approach is straightforward and works well for smaller inputs, but it scans the array sequentially.

Approach 2: Binary Search Using Missing Index Formula (O(log n) time, O(1) space)

The sorted property enables a faster solution with binary search. Instead of counting gaps one by one, compute how many numbers are missing up to index i. The formula is missing(i) = nums[i] - nums[0] - i. It measures the difference between the expected value in a perfect sequence and the actual value in the array. If missing(mid) < k, the k-th missing number lies to the right; otherwise it lies to the left.

Once binary search finds the first index where the missing count becomes at least k, the answer lies between two array elements. Let the previous index be i - 1. You already know how many numbers were missing before that point, so compute the final value as nums[i-1] + (k - missing(i-1)). This avoids scanning every gap and jumps directly to the region containing the answer.

This method works because the missing-count function grows monotonically across the sorted array. Binary search exploits that monotonic behavior to narrow the search space from n elements down to log n comparisons.

Recommended for interviews: The binary search approach. Interviewers expect you to notice the sorted structure and derive the missing(i) formula. Starting with the linear scan demonstrates clear reasoning about gaps, but the optimized binary search shows stronger algorithmic thinking and familiarity with search patterns on monotonic functions.

Solution

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Linear Scan with Gap CountingO(n)O(1)Good for quickly implementing the idea or when the array is small
Binary Search with Missing Count FormulaO(log n)O(1)Best choice for interviews and large arrays since the input is sorted

Video Solution

Leetcode 1060 Missing Element in Sorted Array • Ren Zhang • 6,608 views views

Watch 9 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Missing Element in Sorted Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays