Missing Element in Sorted Array

MediumBinary Searchbinary search

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given a strictly increasing integer array nums and a positive integer k. Consider the integers greater than nums[0] in increasing order and skip those that appear in nums; these are the *missing* numbers. Return the k-th missing number (1-indexed). It may lie beyond the last element of nums. Aim for O(log n) time.

Examples

Input: nums = [4,7,9,10], k = 1
Output: 5
The missing numbers are 5, 6, 8, 11, 12, ...; the first is 5.
Input: nums = [4,7,9,10], k = 3
Output: 8
The third missing number is 8.
Input: nums = [1,2,4], k = 3
Output: 6
The missing numbers are 3, 5, 6, ...; the third is 6.

Constraints

  • `1 <= nums.length <= 5 * 10^4`
  • `1 <= nums[i] <= 10^7`
  • `nums` is strictly increasing
  • `1 <= k <= 10^8`

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More binary search problems