Kth Missing Positive Number (LeetCode 1539): From Linear Scan to Binary Search

The problem

Given a strictly increasing array of positive integers arr and an integer k, return the k-th positive integer missing from the array. For arr = [2,3,4,7,11] and k = 5 the answer is 9.

The key count

If nothing were missing, arr[i] would equal i + 1. So the number of missing values before index i is arr[i] - (i + 1), and this count never decreases.

Binary search on that count

def find_kth_positive(arr, k):
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = (lo + hi) // 2
        if arr[mid] - (mid + 1) < k:
            lo = mid + 1
        else:
            hi = mid
    return lo + k

After the loop, lo elements of the array sit before the answer, so the answer is lo + k. O(log n) time.

How to present it

Start with the O(n + k) walk, then derive the missing-count formula and point out it is monotonic, which is what makes binary search valid. Naming the monotonic property is the part interviewers want to hear. If you want practice explaining monotonic searches under time pressure, Linkjob AI's real-time interview helper can listen in on mock rounds. (Disclosure: I work on Linkjob AI.)