Coding interview: How do you find the kth missing positive with binary search?

What the interviewer evaluates

The surface problem is counting in an array; the core is turning “how many values are missing through index i” into a monotone predicate and then searching its boundary. LeetCode 1539 provides the public problem statement and an Amazon problem-set entry. Amazon’s SDE guidance emphasizes runnable, robust, tested code and edge-case checks. These sources support preparation value, not a fixed interview-frequency claim for any company.

• Whether you write missing(i) = arr[i] - i - 1.
• Whether you prove that the missing count is non-decreasing.
• Whether you handle an answer beyond the last array element.
• Whether you compare scanning, binary search, and direct generation by contract.

30-second answer framework

State that the array uses zero-based indexes. Through arr[i], there are arr[i] positive integers in the value range but only i + 1 observed elements, so the missing count is arr[i] - i - 1. Binary-search the first index with missing(i) >= k. If it is i, the answer is k + i; if no index satisfies it, the answer is after the array and is k + n. Scanning takes O(n), binary search O(log n), and both use O(1) extra space.

Clarifying questions before answering

1. Is the array guaranteed strictly increasing and positive? If not, sorting or deduplication changes the contract.
2. Is k positive, and can values exceed the language’s safe integer range?
3. Is one value required, or all missing values? Returning all values has an output cost.
4. Can the input be streamed without random access? That may favor a scan.
5. Must the original array remain unchanged? The binary-search solution does not mutate it.

Step-by-step deep dive

Step 1: Build the missing-count formula

If the array were continuous, arr[i] would equal i + 1. The difference is the number of positive integers missing from [1, arr[i]]:

missing(i) = arr[i] - (i + 1)
           = arr[i] - i - 1

For arr = [2, 3, 4, 7, 11] and i=3, missing(3) = 7 - 3 - 1 = 3; the missing values are 1, 5, and 6.

Step 2: Use monotonicity for a boundary

Strict increase gives arr[i+1] >= arr[i] + 1. Therefore missing(i+1) >= missing(i), so the count never decreases. Search for the first index with missing(i) >= k: everything before it has too few missing values, while that index and everything after it have at least k.

Step 3: Recover the answer from the boundary

Let the boundary be i. There are i observed array elements before it, and fewer than k missing values before the boundary. The kth missing value is therefore k + i. If no boundary exists, the final missing count is still below k; all n observed elements lie before the answer, so the result is k + n.

Step 4: Implement the binary search

function findKthPositive(arr: number[], k: number): number {
  let left = 0;
  let right = arr.length;

  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);
    const missing = arr[mid] - mid - 1;
    if (missing < k) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }

  return k + left;
}

Using right = n makes the boundary allowed immediately after the array. At termination, left is the first position whose missing count reaches k, so the same k + left formula handles both cases.

Step 5: Prove complexity and test boundaries

Each iteration halves the search interval, giving O(log n) time and constant extra variables. Test arr = [1,2,3,4], k = 2 for 6, arr = [2,3,4,7,11], k = 5 for 9, a sequence missing from 1, a continuous tail, k=1, and a one-element array. Also check integer bounds in the chosen language.

Model high-quality answer

I would define the number of missing positive integers through index i as arr[i] - i - 1. Since the array is strictly increasing, that count is monotone, so I binary-search the first index whose count is at least k. If the boundary is i, the kth missing value is k + i; setting the right boundary to n naturally handles an answer after the maximum array value.

I use a half-open interval [left, right). When missing(mid) is less than k, the boundary is to the right; otherwise I keep mid. The result is k + left, in O(log n) time and O(1) space. I test leading gaps, trailing gaps, a continuous array, a singleton, and several k values, and compare against a scan-based oracle.

Common mistakes

• Writing arr[i] - i and missing the subtract-one term.
• Searching for the last false position but using the first-true answer formula.
• Setting right to n - 1 and mishandling answers after the array.
• Applying the formula when the input is unsorted or contains duplicates.
• Testing only the examples and missing [1,2,3], [2], or a continuous tail.
• Claiming binary search is always faster without discussing sorted input and small-n constants.

Implementation trade-offs

Choose linear scanning or binary search from the data size and boundary contract, then verify the invariant with tests.

Follow-up questions and answers

Why is the missing count monotone?

Strict increase means the next value grows by at least one. When the index grows by one, the value grows by at least one too, so arr[i] - i - 1 cannot decrease.

What if the array is unsorted or has duplicates?

Change the contract first: sort, deduplicate, and retain positive values. Sorting costs at least O(n log n); only then does the original missing-count formula apply. Do not claim O(log n) for unsorted input.

When is a linear scan preferable?

For a short array, one query, or a stream without random access, scanning is simpler. Binary search assumes sorted random-access input and has setup and constant costs.

How would you return the first k missing values?

Find the value boundary, then generate values with an array pointer in O(k) output time. Output work cannot be hidden inside an O(log n) claim.

How do you prevent overflow for large k or values?

Use a safe integer or 64-bit type and check k + left and arr[i] - i - 1. If arbitrary precision is allowed, specify BigInt or the equivalent representation in the interface and tests.

Scoring rubric

A strong candidate derives the monotone predicate, implements a half-open search, and explains the answer formula. A candidate who only recalls code and cannot prove the boundary needs further probing.