Missing Element in Sorted Array solution and explanation
Google
9 more videos on this problem
Leetcode 1060 Missing Element in Sorted ArrayRen Zhang · 11:18 · 6K views
LeetCode 1060. Missing Element in Sorted ArrayHappy Coding · 15:24 · 5K views
Facebook Coding Interview Question | Leetcode 1060 | Missing Element in Sorted ArrayWorkWithGoogler · 8:08 · 2K views
1060. Missing Element in Sorted Array - Leetcode Python SolutionCode with Carter · 14:26 · 1K views
leetcode 中文 | Missing Element in Sorted Array | Google谷歌考題 | Leetcode 1060 | Python今天比昨天厲害 · 20:51 · 1K views
Leetcode 1060. Missing Element in Sorted ArrayVrushali Jadhav · 20:58 · 1K views
1060. Missing Element in Sorted Array | JSer - JavaScript & AlgorithmJSer · 5:24 · 822 views
1060. Missing Element in Sorted Array | English | MediumSimple Code - 단순코드 · 8:48 · 477 views
1060. Missing Element in Sorted Array - Week 5/5 Leetcode July ChallengeProgramming Live with Larry · 18:42 · 446 views
Missing Element in Sorted Array - LeetCode 1060 - Python - Binary SearchAlpha-Code · 22:11 · 223 views
The problem
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 * 1041 <= nums[i] <= 107numsis sorted in ascending order, and all the elements are unique.1 <= k <= 108
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
class Solution:
def missingElement(self, nums: List[int], k: int) -> int:
def missing(i: int) -> int:
return nums[i] - nums[0] - i
n = len(nums)
if k > missing(n - 1):
return nums[n - 1] + k - missing(n - 1)
l, r = 0, n - 1
while l < r:
mid = (l + r) >> 1
if missing(mid) >= k:
r = mid
else:
l = mid + 1
return nums[l - 1] + k - missing(l - 1)class Solution {
public int missingElement(int[] nums, int k) {
int n = nums.length;
if (k > missing(nums, n - 1)) {
return nums[n - 1] + k - missing(nums, n - 1);
}
int l = 0, r = n - 1;
while (l < r) {
int mid = (l + r) >> 1;
if (missing(nums, mid) >= k) {
r = mid;
} else {
l = mid + 1;
}
}
return nums[l - 1] + k - missing(nums, l - 1);
}
private int missing(int[] nums, int i) {
return nums[i] - nums[0] - i;
}
}class Solution {
public:
int missingElement(vector<int>& nums, int k) {
auto missing = [&](int i) {
return nums[i] - nums[0] - i;
};
int n = nums.size();
if (k > missing(n - 1)) {
return nums[n - 1] + k - missing(n - 1);
}
int l = 0, r = n - 1;
while (l < r) {
int mid = (l + r) >> 1;
if (missing(mid) >= k) {
r = mid;
} else {
l = mid + 1;
}
}
return nums[l - 1] + k - missing(l - 1);
}
};func missingElement(nums []int, k int) int {
missing := func(i int) int {
return nums[i] - nums[0] - i
}
n := len(nums)
if k > missing(n-1) {
return nums[n-1] + k - missing(n-1)
}
l, r := 0, n-1
for l < r {
mid := (l + r) >> 1
if missing(mid) >= k {
r = mid
} else {
l = mid + 1
}
}
return nums[l-1] + k - missing(l-1)
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Linear Scan with Gap Counting | O(n) | O(1) | Good for quickly implementing the idea or when the array is small |
| Binary Search with Missing Count Formula | O(log n) | O(1) | Best choice for interviews and large arrays since the input is sorted |
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.