1060. Missing Element in Sorted Array
Problem Description
Given a sorted integer array nums
with unique elements, our task is to find the k-th missing number from the array. A missing number in the array is defined as a number that is not included in the array but falls within the range of the array's first and last elements. For example, if our array is [2, 3, 5, 9]
, and we are looking for the 1st missing number, the answer would be 4
, since it is the first number that does not exist in the array but falls within the range starting from the leftmost number 2
. If we were asked for the 2nd missing number, the answer would be 6
, and so on.
Intuition
The intuition behind the solution comes from understanding how to calculate the missing numbers in a particular segment of the sorted array. In a sorted array, where all elements are unique, the difference between the value of the element at a given position and its index (adjusting for the starting point of the series) tells how many numbers are missing up to that position.
To solve this problem, we can define a helper function missing(i)
that returns the total count of missing numbers up to index i
. Since the array is sorted, we can use binary search to find the smallest index l
such that the count of missing numbers up to l
is less than or equal to k
.
The solution follows these steps:
- Calculate the total number of missing numbers within the entire array. If
k
is greater than this number, we can simply addk
to the last element of the array minus the total missing count. - Otherwise, perform a binary search between the start
l
= 0 and endr
=n
- 1 of the array to find the lowest indexl
where the count of missing numbers is less thank
. - Using the binary search, when the count of missing numbers up to
mid
index is equal to or more thank
, we move the right pointerr
tomid
. Otherwise, we move the left pointerl
tomid + 1
. - Finally, once the binary search is completed, the answer is the number at index
l-1
plusk
minus the total count of missing numbers up tol-1
.
In this approach, we achieve a logarithmic time complexity, making the algorithm efficient even for large arrays.
Learn more about Binary Search patterns.
Solution Approach
The solution implements a binary search algorithm due to the array nums
being sorted in ascending order. This approach is efficient for finding an element or a position within a sorted array in logarithmic time complexity, which is O(log n). The binary search pattern is used to quickly identify the segment of the array where the k-th missing number lies.
The solution has the following key components:
-
A helper function
missing(i)
: this function calculates the total number of missing numbers up to indexi
. This is done by comparing the value atnums[i]
with the starting valuenums[0]
and the indexi
. The mathematical expression isnums[i] - nums[0] - i
. -
The main function
missingElement(nums, k)
: this function uses binary search to find the position where the k-th missing number is. The binary search is carried out with the help of two pointers,l
(left) andr
(right), which define the search boundaries. -
The while loop
while l < r
: it repeatedly splits the array in half to check the count of missing numbers up to the midpoint. Depending on whether the count of missing numbers is less than or greater thank
, it adjusts the search space by moving the left or right pointers. The conditionmissing(mid) >= k
is used to decide if we should move the right pointer. -
Calculating the result: after finding the right segment where the k-th missing number fits, the exact number is obtained using the expression
nums[l - 1] + k - missing(l - 1)
. This accounts for the missing numbers up to the position just before the one found by binary search.
The efficient use of binary search in this sorted array reduces the iteration count from potentially linear (if we were to iterate over each element) to logarithmic, making it suited for large-scale problems.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a small example. Assume we have the following sorted array nums
and we are asked to find the 3rd missing number (k = 3
):
1nums = [1, 2, 4, 7, 10]
To find the 3rd missing number, we perform the following steps:
-
Call the helper function
missing(i)
to calculate the number of missing numbers before several positions in the array. This works as follows:- For
i = 0
(element1
),missing(0)
is0
because there are no missing numbers before the first element. - For
i = 2
(element4
),missing(2)
is4 - 1 - 2 = 1
because there is one number (3
) missing before it.
- For
-
Compare
k
with the total number of missing numbers in the entire array to determine ifk
is within the array's range or beyond. In this case, sincenums
starts with1
and ends with10
, there are10 - 1 - (5 - 1) = 5
missing numbers in total. Sincek = 3
is less than5
, the 3rd missing number is within the range. -
Perform a binary search to find the smallest index
l
such that the count of missing numbers up tol
is less than or equal tok
. Our binary search starts withl = 0
andr = 4
(the last index ofnums
):- First iteration:
mid = (0 + 4)/2 = 2
,missing(mid) = 1 < k
, so updatel = mid + 1 = 3
. - Second iteration:
mid = (3 + 4)/2 = 3
,missing(mid) = 3 (since 3, 5, and 6 are missing before 7) = k
, so updater = mid = 3
. - The loop ends because
l < r
is no longer true.
- First iteration:
-
The final index
l
we found will be3
. The 3rd missing number is not in positionl
orl-1
but after the number atl-1
. Therefore, we calculate the 3rd missing number asnums[l-1] + k - missing(l-1)
. In our case, this isnums[2] + 3 - 1 = 4 + 3 - 1 = 6
.
Thus, our 3rd missing number is 6
. This process of binary search minimized the number of steps needed to find k
, which results in significantly faster execution times for large arrays.
Solution Implementation
1from typing import List
2
3class Solution:
4 def missingElement(self, nums: List[int], k: int) -> int:
5 # Helper function to calculate the number of missing elements
6 # before the current index 'i'
7 def count_missing_before_index(i: int) -> int:
8 # The count is the difference between the current value and the
9 # first value minus the number of steps from the beginning
10 return nums[i] - nums[0] - i
11
12 # Calculate the length of the input array 'nums'
13 num_length = len(nums)
14
15 # If 'k' is greater than the number of missing numbers before the last element
16 # then the missing element is beyond the last element of the array
17 if k > count_missing_before_index(num_length - 1):
18 return nums[num_length - 1] + k - count_missing_before_index(num_length - 1)
19
20 # Initialize left and right pointers for binary search
21 left, right = 0, num_length - 1
22
23 # Use binary search to find the smallest index 'left' such that
24 # the number of missing numbers is at least 'k'
25 while left < right:
26 mid = (left + right) // 2
27 if count_missing_before_index(mid) >= k:
28 right = mid
29 else:
30 left = mid + 1
31
32 # The actual missing element is the element at index 'left - 1' plus
33 # 'k' minus the number of missing numbers before 'left - 1'
34 return nums[left - 1] + k - count_missing_before_index(left - 1)
35
36# Example usage:
37# solution = Solution()
38# result = solution.missingElement([4,7,9,10], 1)
39# print(result) # Outputs 5, which is the first missing number.
40
1class Solution {
2
3 // Function to find the k-th missing element in the sorted array nums
4 public int missingElement(int[] nums, int k) {
5 int len = nums.length;
6
7 // Check if k-th missing number is beyond the last element of the array
8 if (k > missingCount(nums, len - 1)) {
9 return nums[len - 1] + k - missingCount(nums, len - 1);
10 }
11
12 // Binary search initialization
13 int left = 0, right = len - 1;
14
15 // Binary search to find the k-th missing element
16 while (left < right) {
17 int mid = (left + right) / 2; // Find the middle index
18 // Check if missing count from start to mid is >= k,
19 // if true, k-th missing number is to the left side of mid
20 if (missingCount(nums, mid) >= k) {
21 right = mid;
22 } else {
23 // Otherwise, k-th missing number is to the right side of mid
24 left = mid + 1;
25 }
26 }
27
28 // Once binary search is complete, compute and return the k-th missing element
29 return nums[left - 1] + k - missingCount(nums, left - 1);
30 }
31
32 // Helper function to calculate the number of missing numbers from start till index i
33 private int missingCount(int[] nums, int idx) {
34 return nums[idx] - nums[0] - idx;
35 }
36}
37
1class Solution {
2public:
3 // Function to find the k-th missing element in a sorted array.
4 int missingElement(vector<int>& nums, int k) {
5 // Lambda function to calculate the number of missing elements
6 // up to the index `i` in the sorted array.
7 auto countMissingUpToIndex = [&](int index) {
8 return nums[index] - nums[0] - index;
9 };
10
11 // Get the size of the input array.
12 int size = nums.size();
13
14 // If k is beyond the range of missing numbers in the array,
15 // calculate the result directly.
16 if (k > countMissingUpToIndex(size - 1)) {
17 return nums[size - 1] + k - countMissingUpToIndex(size - 1);
18 }
19
20 // Initialize binary search bounds.
21 int left = 0, right = size - 1;
22
23 // Perform binary search to find the smallest element
24 // such that the number of missing elements up to that
25 // element is equal or greater than k.
26 while (left < right) {
27 int mid = left + (right - left) / 2;
28 if (countMissingUpToIndex(mid) >= k) {
29 right = mid;
30 } else {
31 left = mid + 1;
32 }
33 }
34
35 // Calculate the k-th missing element using the
36 // element at index `left - 1`.
37 return nums[left - 1] + k - countMissingUpToIndex(left - 1);
38 }
39};
40
1// Function to find the k-th missing element in a sorted array.
2function missingElement(nums: number[], k: number): number {
3 // Lambda function to calculate the number of missing elements
4 // up to the index `i` in the sorted array.
5 const countMissingUpToIndex = (index: number) => {
6 return nums[index] - nums[0] - index;
7 };
8
9 // Get the size of the input array.
10 const size: number = nums.length;
11
12 // If k is beyond the range of missing numbers in the array,
13 // return the k-th element beyond the last element.
14 if (k > countMissingUpToIndex(size - 1)) {
15 return nums[size - 1] + k - countMissingUpToIndex(size - 1);
16 }
17
18 // Initialize binary search bounds.
19 let left: number = 0;
20 let right: number = size - 1;
21
22 // Perform a binary search to find the smallest element
23 // such that the number of missing elements up to that
24 // element is equal to or greater than k.
25 while (left < right) {
26 let mid: number = left + Math.floor((right - left) / 2);
27 if (countMissingUpToIndex(mid) >= k) {
28 right = mid;
29 } else {
30 left = mid + 1;
31 }
32 }
33
34 // Calculate the k-th missing element using the
35 // element at index `left - 1`.
36 return nums[left - 1] + k - countMissingUpToIndex(left - 1);
37}
38
Time and Space Complexity
Time Complexity
The time complexity of the provided code can be analyzed as follows:
- The
missing
function is a simple calculation that performs in constant time, O(1). - The
missingElement
function runs a binary search algorithm over the array of sizen
. Binary search cuts the search space in half with each iteration, resulting in a logarithmic time complexity, O(log n). - Since the missing function is called within the binary search loop, and it is called in constant time, it does not affect the overall time complexity of O(log n).
Therefore, the overall time complexity of the code is O(log n)
.
Space Complexity
The space complexity can be analyzed as follows:
- The given solution uses only a fixed amount of extra space for variables such as
n, l, r, mid
, which does not depend on the input size. - No additional data structures or recursive calls that use additional stack space are made.
Hence, the overall space complexity is O(1)
, which implies constant space is used regardless of the input size.
Learn more about how to find time and space complexity quickly using problem constraints.
Which algorithm is best for finding the shortest distance between two points in an unweighted graph?
Recommended Readings
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.