Kth Missing Positive

Find the k-th missing positive integer from a sorted array efficiently.

binary search arrays mathematics

Write a function `find_kth_missing(arr, k)` that takes a strictly increasing list of positive integers `arr` and an integer `k`, and returns the k-th positive integer that is missing from the array.

Positive integers start from 1. For example, if `arr = [2, 3, 4, 7, 11]`, the missing positive integers are `1, 5, 6, 8, 9, 10, 12, ...` so the 5th missing is `9`.

Your solution must run in **O(log n)** time, where `n = len(arr)`. You may assume `1 <= len(arr) <= 10^5`, `1 <= k <= 10^9`, and `arr` contains distinct positive integers in strictly increasing order.

Constraints

1 <= len(arr) <= 10^5\n1 <= k <= 10^9\narr[i] >= 1\narr is strictly increasing\nExpected time complexity: O(log n)\nExpected space complexity: O(1)

Example

>>> find_kth_missing([2,3,4,7,11], 5)
9
>>> find_kth_missing([1,2,3,4], 2)
6
>>> find_kth_missing([5,6,7], 1)
1
>>> find_kth_missing([], 3)
3

20 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think about how many numbers are missing before each array element.

Use binary search on the index of the array to find where the k-th missing lies.

Once you find the right index, compute the answer using the number of missing before that index.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.