Kth Missing Positive Integer

L5 Medium Binary Search

Concept

Counting how many positive integers are missing up to each array element turns "find the kth missing" into a search over an accumulated count.

Given a sorted array of distinct positive integers arr, consider all positive integers not present in the array. Return the kth missing one.

Examples

▸ arr = [2, 3, 4, 7, 11], k = 5

→ 9

▸ arr = [1, 2, 3, 4], k = 2

→ 6

▸ arr = [], k = 3

→ 3

Progressive Hints

Hint 1 · Nudge

As you move through the array, count how many integers have been skipped so far.

Hint 2 · Plan

Walk the array while tracking how many positive integers are missing up to the current element. When that number reaches k, step back from the current element by exactly the overshoot.

Hint 3 · Approach

For each i, arr[i], the missing count so far is arr[i] - (i + 1). When missing >= k, return arr[i] - (missing - k). If it never reaches k, return the last element plus the difference.

Output

// Run your code to see the output here.