Kth Missing Positive Number

Given an array arr of positive integers sorted in a strictly increasing order, and an integer k.

Find the kth positive integer that is missing from this array.

Example

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

Output: 9

Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,...]. The 5th missing positive integer is 9.


Solution

Python solution

def binary_search(arr: List[int], k: int) -> int: if arr[0] > k: return k

1l = 0
2r = len(arr) - 1
3while l < r:
4    mid = (l + r) // 2
5    x = arr[mid] if mid < len(arr) else 10**9
6    if x - mid - 1 >= k:
7        r = mid
8    else:
9        l = mid + 1
10
11return k - (arr[l - 1] - (l - 1) - 1) + arr[l - 1]

Java Solution

public int binarySearch(int[] arr) { if (arr[0] > k) { return k; }

1int l = 0;
2int r = arr.length - 1;
3while (l < r) {
4    int mid = (l + r) / 2;
5    int x = mid < arr.length ? arr[mid] : Integer.MAX_VALUE;
6    if (x - mid - 1 >= k) {
7        r = mid;
8    } else {
9        l = mid + 1;
10    }
11}
12
13return k - (arr[l - 1] - (l - 1) - 1) + arr[l - 1];

}

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How does quick sort divide the problem into subproblems?

Solution Implementation


Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following is a good use case for backtracking?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Tired of the LeetCode Grind?

Our structured approach teaches you the patterns behind problems, so you can confidently solve any challenge. Get started now to land your dream tech job.

Get Started

🪄