1060. Missing Element in Sorted Array

MediumArrayBinary Search
Leetcode Link

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:

  1. 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.
  2. 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.
  3. 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.
  4. 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

How does merge sort divide the problem into subproblems?

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.

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

In a binary min heap, the maximum element can be found in:

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

1nums = [1, 2, 4, 7, 10]

To find the 3rd missing number, we perform the following steps:

  1. 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.

  2. 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.

  3. 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.

  4. 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
Not Sure What to Study? Take the 2-min Quiz：

Which technique can we use to find the middle of a linked list?

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.

Fast Track Your Learning with Our Quick Skills Quiz:

Which data structure is used to implement priority queue?

Recommended Readings

Binary Search Speedrun

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 - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

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 Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫