Kth Missing Positive Number

The problem. Given an array arr of positive integers sorted in strictly increasing order, and an integer k, return the k-th positive integer missing from the array.

Example

arr = [2, 3, 4, 7, 11], k = 5  ->  9    (missing 1, 5, 6, 8, 9, ...)
arr = [1, 2, 3, 4], k = 2      ->  6    (missing 5, 6, ...)
arr = [5, 6, 7], k = 3         ->  3    (missing 1, 2, 3, ...)

The idea: count what's missing before each value

If nothing were missing, arr[i] would be i + 1. So `arr[i] - (i + 1)` numbers are missing below arr[i]. That count never decreases as i grows — a sorted sequence hiding inside the array. Binary search it for the first index i with at least k missing. Then the answer sits after the first i values of the array and after k missing numbers, so it's exactly `i + k`. (If every value has fewer than k missing, i is the array's length and the formula still works.)

1. Walk through the array

Start with the answer k, as if nothing were in the array. Each array value at or below the answer takes up a spot, pushing the answer one further.

1function findKthPositive(arr, k) {2  for (const value of arr) {3    if (value <= k) k++;                // a value at or below the answer pushes it one further4    else break;5  }6  return k;7}

Time O(n), space O(1). Short and clever — and the follow-up asks for better than O(n).

2. Binary search on the missing count

1function findKthPositive(arr, k) {2  let low = 0;3  let high = arr.length;4  while (low < high) {5    const mid = low + Math.floor((high - low) / 2);6    if (arr[mid] - (mid + 1) < k) low = mid + 1;   // fewer than k missing before arr[mid]7    else high = mid;8  }9  return low + k;                         // low array values and k missing numbers come first10}

Time O(log n), space O(1). The search isn't over the values or the answers but over a derived sorted sequence — the missing counts — computed on the fly at each mid.

Comparing the approaches

Edge cases to test

Variations