Missing Element in sorted array

XXX. Missing Element in Sorted Array

Binary Search

Array

Problem Statement:

Given a sorted array nums where each element is unique, find the kth missing number starting from nums[0].

• Array is strictly increasing
• Start counting missing numbers from first element
• Find kth missing number in sequence

Implementations:

Java Solution:

// GREAT BINARY SEARCH PROBLEM

// KEY: Find the largest element that has missing(idx) < k
// SO IT MUST BE IN THE INTERVAL OF THAT INDEX and the next ELEMENT
// Then add k - missing(idx) to find the missing number (this is easy)                
class Solution {
    // Calculate missing numbers up to index
    int missing(int idx, int[] nums) {
        return nums[idx] - nums[0] - idx;
    }
    
    public int missingElement(int[] nums, int k) {
        int n = nums.length;
        int left = 0, right = n - 1;
        int pivot, ans = -1;
        
        while (left <= right) {
            pivot = left + (right - left) / 2;
            
            if (missing(pivot, nums) < k) {
                ans = pivot;
                left = pivot + 1;
            } else 
                right = pivot - 1;
        }
        
        return nums[ans] + k - missing(ans, nums);
    }
}

Python Solution:

def missingElement(self, nums: List[int], k: int) -> int:
    def missing(idx: int) -> int:
        return nums[idx] - nums[0] - idx
    
    n = len(nums)
    left, right = 0, n - 1
    ans = -1
    
    while left <= right:
        pivot = left + (right - left) // 2
        
        if missing(pivot) < k:
            ans = pivot
            left = pivot + 1
        else:
            right = pivot - 1
    
    return nums[ans] + k - missing(ans)

C++ Solution:

class Solution {
private:
    int missing(int idx, vector& nums) {
        return nums[idx] - nums[0] - idx;
    }
    
public:
    int missingElement(vector& nums, int k) {
        int n = nums.size();
        int left = 0, right = n - 1;
        int pivot, ans = -1;
        
        while (left <= right) {
            pivot = left + (right - left) / 2;
            
            if (missing(pivot, nums) < k) {
                ans = pivot;
                left = pivot + 1;
            } else
                right = pivot - 1;
        }
        
        return nums[ans] + k - missing(ans, nums);
    }
};

Example:

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

• Missing numbers from 4: 5,6,8
• Binary search steps:
  • mid = 1: missing(1) = 1 < k
  • mid = 3: missing(3) = 3 = k
  • mid = 2: missing(2) = 2 < k
• Answer: nums[2] + (3 - 2) = 9 + 1 = 8

Complexity:

Time Complexity: O(log n), binary search
Space Complexity: O(1), constant space

Implementation Notes:

• **Missing Count Logic**:
  • nums[idx] - nums[0] - idx calculates missing numbers
  • Starts counting from first element
  • Handles gaps efficiently
• **Binary Search Approach**:
  • Search based on missing count
  • Track last valid position
  • Calculate final answer using position