LeetCode 1060 - Missing Element in Sorted Array

LeetCode Problem 1060

Difficulty: 🟡 Medium
Topics: Array, Binary Search

Solution

Problem Understanding

The problem asks us to find the k-th missing number in a sorted, strictly increasing array of unique integers. Given nums and an integer k, we need to identify the number that is missing from the sequence formed by consecutive integers starting from nums[0].

The input nums represents known elements in a sorted sequence, but some integers between nums[0] and nums[-1] (and potentially beyond) are missing. The integer k specifies which missing number to return, counting from the first missing number in order.

The output is a single integer, the k-th missing number. Constraints guarantee that the array can be fairly large (up to 5 * 10^4) and k can also be very large (up to 10^8). This implies that naive linear solutions that check each number sequentially will be too slow for large input ranges.

Key observations include that the array is strictly increasing, so the number of missing elements between two consecutive elements can be calculated as nums[i+1] - nums[i] - 1. Edge cases include situations where the missing number is before the first array element, after the last array element, or exactly between two elements.

Approaches

The brute-force approach iterates through every integer starting from nums[0], counting missing numbers until we reach the k-th missing one. This approach is guaranteed to work but is inefficient. If nums[-1] is very large and k is also large, it may require checking millions of numbers, leading to a time complexity of O(N + k), which is not feasible for the upper constraint bounds.

The optimal approach leverages the fact that the array is sorted. We can compute the number of missing elements up to any index i using nums[i] - nums[0] - i. This gives us a strictly increasing function representing cumulative missing counts. Since it is monotonic, we can perform a binary search to efficiently find the first index where the cumulative number of missing numbers is at least k. Once the proper interval is found, the k-th missing number can be computed directly. This reduces the time complexity to O(log N) and uses O(1) extra space.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(k + n)	O(1)	Iterate sequentially counting missing numbers
Optimal	O(log n)	O(1)	Binary search using cumulative missing numbers formula

Algorithm Walkthrough

1. Calculate missing numbers at index i: Define a helper function missing(i) that computes the total number of missing numbers from nums[0] to nums[i] using the formula nums[i] - nums[0] - i.
2. Check if k-th missing number is beyond the last element: If k > missing(n-1), then the k-th missing number is after nums[-1] and can be calculated as nums[-1] + (k - missing(n-1)).
3. Perform binary search: Initialize left as 0 and right as n - 1. Perform standard binary search to find the first index idx such that missing(idx) >= k. In each iteration, calculate mid = (left + right) // 2. If missing(mid) < k, move left to mid + 1; otherwise, move right to mid.
4. Calculate the k-th missing number: After binary search, left points to the first index where cumulative missing numbers are greater than or equal to k. The k-th missing number can be calculated as nums[left - 1] + (k - missing(left - 1)).

Why it works: The cumulative missing count is strictly increasing, so the binary search guarantees that we find the correct interval where the k-th missing number falls. Using the formula nums[i] - nums[0] - i ensures that the computation of missing numbers is accurate and monotonic.

Python Solution

from typing import List

class Solution:
    def missingElement(self, nums: List[int], k: int) -> int:
        n = len(nums)
        
        # Helper function to compute missing numbers until index i
        def missing(index: int) -> int:
            return nums[index] - nums[0] - index
        
        # If k-th missing is beyond the last element
        if k > missing(n - 1):
            return nums[-1] + (k - missing(n - 1))
        
        left, right = 0, n - 1
        while left < right:
            mid = (left + right) // 2
            if missing(mid) < k:
                left = mid + 1
            else:
                right = mid
        
        # k-th missing number is between nums[left - 1] and nums[left]
        return nums[left - 1] + (k - missing(left - 1))

This implementation first checks if the k-th missing number lies beyond the last element. If not, it performs binary search on the cumulative missing numbers. The helper function ensures clear and correct computation of the missing count. The final calculation adjusts from the previous known element to reach the k-th missing number.

Go Solution

func missingElement(nums []int, k int) int {
    n := len(nums)
    
    // Helper function to calculate missing numbers until index i
    missing := func(index int) int {
        return nums[index] - nums[0] - index
    }
    
    // If k-th missing is beyond the last element
    if k > missing(n - 1) {
        return nums[n - 1] + (k - missing(n - 1))
    }
    
    left, right := 0, n - 1
    for left < right {
        mid := (left + right) / 2
        if missing(mid) < k {
            left = mid + 1
        } else {
            right = mid
        }
    }
    
    return nums[left - 1] + (k - missing(left - 1))
}

The Go implementation mirrors the Python logic. Differences include using an inline function for the missing calculation and integer division with /. Slices handle dynamic lengths naturally. Overflow is not an issue under the problem constraints.

Worked Examples

Example 1: nums = [4,7,9,10], k = 1

Step	left	right	mid	missing(mid)	Action
1	0	3	1	2	missing(1) >= k → right = 1
2	0	1	0	0	missing(0) < k → left = 1

k-th missing = nums[0] + (1 - missing(0)) = 4 + 1 = 5

Example 2: nums = [4,7,9,10], k = 3

Step	left	right	mid	missing(mid)	Action
1	0	3	1	2	missing(1) < k → left = 2
2	2	3	2	4	missing(2) >= k → right = 2

k-th missing = nums[1] + (3 - missing(1)) = 7 + (3-2) = 8

Example 3: nums = [1,2,4], k = 3

Step	left	right	mid	missing(mid)	Action
1	0	2	1	0	missing(1) < k → left = 2

k-th missing = nums[1] + (3 - missing(1)) = 2 + (3-0) = 5 → wait correction: missing(1) = nums[1]-nums[0]-1=2-1-1=0, then 3-0=3, nums[1]+3=2+3=5. Correct, but the missing numbers are [3,5,6], 3rd missing=6 → must be careful: nums[left-1]=2, k - missing(left-1)=3-0=3 → 2+3=5 → hmm, missing numbers counting from nums[0]?

Check: missing(i)=nums[i]-nums[0]-i: missing(0)=1-1-0=0, missing(1)=2-1-1=0, missing(2)=4-1-2=1 → total missing up to last index=1, k=3>1 → return nums[-1]+(3-1)=4+2=6, correct. Yes, works.)

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log n)	Binary search on the array of length n
Space	O(1)	Constant extra space; only indices and helper function

This is efficient because the cumulative missing numbers function is strictly increasing, allowing logarithmic search instead of linear iteration.

Test Cases

# Provided examples
assert Solution().