medium Missing Element in Sorted Array

Problem Statement

Given an array arr containing unique integers in the ascending order, and integer k, return the k^th missing number starting from the arr[0].

The missing numbers are those that are not present in the array, and greater than arr[0].

Examples

Example 1:
- Input: arr = [3, 5, 6, 7], k = 2
- Expected Output: 8
- Justification: The missing numbers in sequence are 4 and 8. The 2nd missing number is 8.
Example 2:
- Input: arr = [1, 2, 4, 8], k = 3
- Expected Output: 6
- Justification: The missing numbers are 3, 5, 6, etc. The 3rd missing number is 6.
Example 3:
- Input: arr = [2, 3, 4, 7, 8, 10, 11], k = 2
- Expected Output: 6
- Justification: The missing numbers in this sequence start from 5, 6, 9... The 2nd missing number in this sequence is 6.

Try it yourself

Try solving this question here:

🎯 STRICT STANDOUT — Missing Element in Sorted Array — problem

0. Pattern family

Family: Binary search on missing-count prefix

1. Why / judgment (K3)

Sorted unique array; missing numbers between nums[0] and nums[i] equal nums[i]-nums[0]-i. Find smallest i where missing-count ≥ k; answer is numeric. This is binary search on index with monotone predicate — not linear scan.

2. Worked complexity / derivation (K11)

O(log n) binary search + O(1) missing(i). Linear O(n) also correct but weaker.

3. Pattern + recognition + when-NOT (K12)

Name: BINARY SEARCH ON MISSING PREFIX

Recognition: sorted array with gaps; k-th missing number from start of array.

When-NOT: Unsorted → sort first or set. Missing positive from 1..n cyclic sort. k beyond end → extend past last.

4. Edge hand-run (K13)

nums=[4,7,9,10] k=1 → 5; k=3 → 8. k past end: nums=[1,2,4] k=3 → 6.

5. Interviewer follow-ups & drills

Q1. Predicate?
Model answer: missing(mid)=nums[mid]-nums[0]-mid ≥ k → go left for first such.

Q2. After loop formula?
Model answer: nums[0]+k+index_adjustment using final lo/hi.

Q3. Duplicates?
Model answer: Problem assumes unique; dups break missing formula.

✅ Solution Missing Element in Sorted Array

Problem Statement

Given an array arr containing unique integers in the ascending order, and integer k, return the k^th missing number starting from the arr[0].

The missing numbers are those that are not present in the array, and greater than arr[0].

Examples

Example 1:
- Input: arr = [3, 5, 6, 7], k = 2
- Expected Output: 8
- Justification: The missing numbers in sequence are 4 and 8. The 2nd missing number is 8.
Example 2:
- Input: arr = [1, 2, 4, 8], k = 3
- Expected Output: 6
- Justification: The missing numbers are 3, 5, 6, etc. The 3rd missing number is 6.
Example 3:
- Input: arr = [2, 3, 4, 7, 8, 10, 11], k = 2
- Expected Output: 6
- Justification: The missing numbers in this sequence start from 5, 6, 9... The 2nd missing number in this sequence is 6.

Solution

To solve this problem, we will use a binary search approach. This method is efficient because it significantly reduces the number of elements we need to inspect in the sorted array. By comparing the number of missing elements at the midpoint of the array with k, we can determine whether to search in the left or right half of the array.

This approach works effectively because the array is sorted, and we can calculate the number of missing elements up to any point. Since we're dealing with missing elements in a sequence, leveraging the sorted nature of the array allows us to quickly home in on the correct position, making this method both time-efficient and intuitive.

Step-by-step Algorithm

Initialize Variables:
- Set n to the length of the input array nums.
- Initialize two pointers left = 0 and right = n - 1 for binary search.
Perform Binary Search:
- While left is less than right:
  - Calculate mid as right - (right - left) / 2. This finds the middle index between left and right.
  - Check if the number of missing elements up to mid is less than k.
    - This is done by nums[mid] - nums[0] - mid.
  - If the missing count is less than k, set left to mid. This moves the search to the right half of the current segment.
  - Otherwise, set right to mid - 1. This moves the search to the left half.
Calculate and Return Result:
- After exiting the loop, calculate the k-th missing element as nums[0] + k + left.
- Return this value.

Algorithm Walkthrough for Updated Example 3:

Input: arr = [2, 3, 4, 7, 8, 10, 11], k = 2
Initialization:
- n = 7 (length of array)
- left = 0, right = 6
Binary Search Steps:
- Iteration 1:
  - mid = 6 - (6 - 0) / 2 = 3
  - Missing elements till mid = arr[3] - arr[0] - (3 - 0) = 7 - 2 - 3 = 2
  - Since Missing Count (2) is equal to k, move right pointer: right = mid - 1 = 3 - 1 = 2
- Iteration 2:
  - mid = 2 - (2 - 0) / 2 = 1
  - Missing count = arr[1] - arr[0] - (1 - 0) = 3 - 2 - 1 = 0
  - Since Missing Count (1) is less than k, move left pointer: left = mid = 1
- Iteration 3:
  - mid = 2 - (2 - 1) / 2 = 2 - 0 = 2
  - Missing count = arr[2] - arr[0] - (2 - 0) = 4 - 2 - 2 = 0
  - Since Missing Count (2) is less than k, move left pointer: left = mid = 2
Iteration 3:
- since left > right, break the loop.
Result Calculation:
- Exiting loop with left = 2
- Calculate result: nums[0] + k + left = 2 + 2 + 2 = 6
Final Output: 6.

Code

java

public class Solution {

  // Method to find the k-th missing element in a sorted array
  public int findMissingElement(int[] nums, int k) {
    int n = nums.length; // Length of the array
    int left = 0, right = n - 1; // Initialize pointers for binary search

    // Perform binary search
    while (left < right) {
      int mid = right - (right - left) / 2; // Calculate the middle index
      // If the count of missing numbers until mid is less than k, move left pointer
      if (nums[mid] - nums[0] - mid < k) {
        left = mid;
      } else { // Otherwise, move right pointer
        right = mid - 1;
      }
    }

    // Calculate and return the k-th missing element
    return nums[0] + k + left;
  }

  // Main method to test the algorithm with examples
  public static void main(String[] args) {
    Solution solution = new Solution();
    System.out.println(
      solution.findMissingElement(new int[] { 3, 5, 6, 7 }, 2)
    ); // Example 1
    System.out.println(
      solution.findMissingElement(new int[] { 1, 2, 4, 8 }, 3)
    ); // Example 2
    System.out.println(
      solution.findMissingElement(new int[] { 2, 3, 4, 7, 8, 10, 11 }, 2)
    ); // Updated Example 3
  }
}

Complexity Analysis

Time Complexity: O(log n)
- The algorithm uses binary search, dividing the array in half each step, leading to logarithmic time complexity.
Space Complexity: O(1)
- Only a constant amount of extra space is used in the algorithm, regardless of the input size.

🎯 STRICT STANDOUT — Solution Missing Element in Sorted Array

0. Pattern family

Family: Binary search on missing count

1. Why / judgment (K3)

Implement missing(i) = nums[i] - nums[0] - i. Binary search first index with missing≥k; answer = nums[0] + k + (offset from how many present before). Trace lo/hi on 2-element array to kill off-by-ones.

2. Worked complexity / derivation (K11)

O(log n) comparisons. O(1) space. Linear walk of gaps O(n) acceptable but not standout.

3. Pattern + recognition + when-NOT (K12)

Name: MISSING-COUNT BINARY SEARCH

Recognition: sorted unique; k-th hole after nums[0].

When-NOT: k-th missing positive starting at 1 with unsorted arr (LC1539 variant still BS). Hash set O(n).

4. Edge hand-run (K13)

[4,7,9,10], k=1: missing(0)=0, missing(1)=2 → answer 5.
k=4: beyond 10−4−3=3 missing in array → 4th is 11? count carefully → 11.

5. Interviewer follow-ups & drills

Q1. 2-element [1,3] k=1?
Model answer: missing mid; lo/hi converge to hole 2.

Q2. k larger than total holes in array?
Model answer: Extend past nums[-1]: ans = nums[-1] + (k - missing(n-1)).

Q3. Why sorted required?
Model answer: missing(i) monotone only if sorted ascending unique.

🧩 Pattern · Arrays

Recognize it: Scan once tracking what you need (running max/sum), or precompute a prefix-sum / hash → turn O(n²) into O(n).

▶ Visualize this problem (step it, predict each fork)

⛶ Open this problem debugger in explore mode

🤖 Don't fully get this? Learn it with Claude

Stuck on Missing Element in Sorted Array? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Missing Element in Sorted Array** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Missing Element in Sorted Array** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Missing Element in Sorted Array**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Missing Element in Sorted Array**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Longest Palindromic Subsequence Maximum Level Sum of a Binary Tree →