Missing Element in Sorted Array

Problem Statement

The task requires writing a function that, given a sorted integer array nums where all elements are unique, identifies the kth missing number from a sequence starting from the smallest value in nums. The series is sorted in ascending order and there are no repeating values. Each entry in the array nums represents numbers that exist, therefore the "missing" numbers are those integers that do not appear between the smallest and largest values inclusive of the array bounds. The value of k specifies how many steps deep into the sequence of missing numbers we need to go to fetch the result.

Examples

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

Approach and Intuition

Here's a straightforward plan based on the problem description and constraints:

1. First, we need to locate the sequence of missing numbers:

   • The potential sequence can be conceptualized as all the integers between the smallest (nums[0]) and beyond the largest element (nums[-1]) of the array, excluding the numbers that are actually present in nums.

2. Given the nums is in sorted ascending order and consists of unique elements, one can efficiently determine the missing numbers:

   • Start iterating from the smallest number in the array.
   • For each expected consecutive number, check against the actual numbers in nums. If a number is absent, count it as missing.

3. However, iterating through the complete range of numbers might not be efficient considering the constraints allow for a very large k and array size. An optimal solution requires us to not explicitly track every missing number:

   • The count of missing numbers between two consecutive numbers (say nums[i] and nums[i+1]) is (nums[i+1] - nums[i] - 1).
   • Accumulate this count while tracking how many total numbers have been missed until the accumulated missing count is greater than or equal to k.

4. If the sum of missing numbers up to the last element of nums is less than k, continue counting into the numbers greater than the last element of nums.

5. Return the specific kth missing number:

   • This would be a construction using the last reference point in nums and the excess count needed to reach k. For instance, if the last number checked was nums[i] and we need 2 more missing numbers to reach k, then the result is nums[i] + 2 (assuming no further increments in the sequence within nums).

Solutions

class Solution {
public:
    int findMissing(vector<int>& arr, int k) {
        int size = arr.size();
            
        for (int j = 1; j < size; ++j) {
            int gapCount = arr[j] - arr[j - 1] - 1;
            if (gapCount >= k) {
                return arr[j - 1] + k;
            }
            k -= gapCount;
        }
            
        return arr[size - 1] + k;
    }
};