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 add k to the last element of the array minus the total missing count.
Otherwise, perform a binary search between the start l = 0 and end r = n - 1 of the array to find the lowest index l where the count of missing numbers is less than k.
Using the binary search, when the count of missing numbers up to mid index is equal to or more than k, we move the right pointer r to mid. Otherwise, we move the left pointer l to mid + 1.
Finally, once the binary search is completed, the answer is the number at index l-1 plus k minus the total count of missing numbers up to l-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 index i. This is done by comparing the value at nums[i] with the starting value nums[0] and the index i. The mathematical expression is nums[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) and r (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 than k, it adjusts the search space by moving the left or right pointers. The condition missing(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 Evaluator

Example 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):

nums = [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 (element 1), missing(0) is 0 because there are no missing numbers before the first element.
- For i = 2 (element 4), missing(2) is 4 - 1 - 2 = 1 because there is one number (3) missing before it.
Compare k with the total number of missing numbers in the entire array to determine if k is within the array's range or beyond. In this case, since nums starts with 1 and ends with 10, there are 10 - 1 - (5 - 1) = 5 missing numbers in total. Since k = 3 is less than 5, 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 to l is less than or equal to k. Our binary search starts with l = 0 and r = 4 (the last index of nums):
- First iteration: mid = (0 + 4)/2 = 2, missing(mid) = 1 < k, so update l = mid + 1 = 3.
- Second iteration: mid = (3 + 4)/2 = 3, missing(mid) = 3 (since 3, 5, and 6 are missing before 7) = k, so update r = mid = 3.
- The loop ends because l < r is no longer true.
The final index l we found will be 3. The 3rd missing number is not in position l or l-1 but after the number at l-1. Therefore, we calculate the 3rd missing number as nums[l-1] + k - missing(l-1). In our case, this is nums[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 size n. 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

dp[i] = dp[i] + 1

dp[i] = dp[i] + dp[i - 1]

dp[i] = (dp[i] + dp[j] + 1) for j in 0 to i

dp[i] = max(dp[i], dp[j] + 1) for j in 0 to i

I don’t know