☕ DSA Java Articles

Topics › Binary Search › BS on Answers

Kth Missing Positive Number

Medium TUF ID 600 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given a strictly increasing array arr of positive integers and an integer k. Consider the positive integers 1, 2, 3, ... that do not appear in arr, in increasing order. Return the k-th of them.

Constraints: 1 ≤ n ≤ 1000, 1 ≤ arr[i] ≤ 1000, 1 ≤ k ≤ 1000, arr[i] < arr[j] for i < j.

Example 1

arr = [2, 3, 4, 7, 11], k = 5
answer = 9          // missing numbers are 1, 5, 6, 8, 9, 10, 12, ...; the 5th is 9

Example 2

arr = [1, 2, 3, 4], k = 2
answer = 6          // nothing is missing inside the array, so the missing numbers start at 5: 5, 6, 7, ...

Approach 1: Brute force, count the missing numbers one by one

Intuition. Do exactly what the statement says. Walk through the positive integers starting at 1, and for each one ask “is it in the array?”. A hash set answers that in constant time. Count the ones that are absent and stop at the k-th.

Algorithm.

  1. Put every element of arr into a set.
  2. Set missing = 0, num = 0.
  3. While missing < k: increment num; if num is not in the set, increment missing.
  4. Return num.
static int bruteForce(int[] arr, int k) {
    Set<Integer> present = new HashSet<>();
    for (int x : arr) present.add(x);
    int missing = 0, num = 0;
    while (missing < k) {
        num++;
        if (!present.contains(num)) missing++;
    }
    return num;
}

Complexity. Time O(n + k): the loop stops once k missing numbers have been found, and it skips at most n present numbers along the way, so it runs at most n + k times. Space O(n) for the set.

For the given limits this is instant, but it ignores the fact that the array is sorted, and it scales with k rather than with log n.

Approach 2: Better, one pass that shifts the answer

Intuition. Suppose the array were empty. Then the k-th missing positive is simply k. Now add the array elements back one at a time from the left. An element x ≤ k occupies a slot among the first k positive integers, which pushes the k-th missing number one step to the right: the new answer is k + 1. Repeating this for every element that is not larger than the current answer gives the final answer. Because the array is strictly increasing, once an element exceeds the running answer, all later elements do too and cannot affect it, so we can stop.

Algorithm.

  1. For each x in arr from left to right:
    • If x ≤ k, increment k.
    • Otherwise stop.
  2. Return k.
static int better(int[] arr, int k) {
    for (int x : arr) {
        if (x <= k) k++;
        else break;
    }
    return k;
}

Complexity. Time O(n): one pass, often shorter because of the early break. Space O(1).

Trace on arr = [2, 3, 4, 7, 11], k = 5: 2 ≤ 5 gives k = 6; 3 ≤ 6 gives 7; 4 ≤ 7 gives 8; 7 ≤ 8 gives 9; 11 > 9, stop. Answer 9.

Why is “x ≤ k then k++” correct rather than, say, “x ≤ original k”? Because each time we bump k, the range [1, k] grows by one, and the next array element must be compared with the new range. The invariant after processing the first i elements is: k equals the k-th missing positive if the array consisted only of those i elements.

Approach 3: Optimal, binary search on the index

Intuition. Use the sortedness properly. For index i, how many positive integers smaller than arr[i] are missing? If nothing were missing, the element at index i would be i + 1 (positions are 1, 2, 3, ...). The actual element is arr[i], so exactly

missing(i) = arr[i] - (i + 1)

positives are missing before arr[i]. Because arr is strictly increasing, missing(i) is non-decreasing in i: each step either keeps it (consecutive values) or raises it (a gap). We are looking for the first index whose missing count is at least k; the k-th missing number lies just before that element. Standard binary search for the first index with missing(i) ≥ k: afterwards hi is the last index with missing(hi) < k and lo = hi + 1.

With hi known, the answer is arr[hi] + (k - missing(hi)): start from arr[hi], which has missing(hi) missing numbers before it, and count k - missing(hi) more positions forward (all of which are missing, because the next array element arr[hi+1] has missing ≥ k and therefore comes after the k-th gap). Substituting missing(hi) = arr[hi] - hi - 1 simplifies that to hi + 1 + k, which is lo + k. The arr[hi] terms cancel, so the formula also works when hi = -1 (the answer is before the first element) and when hi = n - 1 (the answer is past the end).

Algorithm.

  1. Set lo = 0, hi = n - 1.
  2. While lo ≤ hi:
    • mid = lo + (hi - lo) / 2, missing = arr[mid] - (mid + 1).
    • If missing < k, set lo = mid + 1; else set hi = mid - 1.
  3. Return lo + k.
static int optimal(int[] arr, int k) {
    int lo = 0, hi = arr.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        int missing = arr[mid] - (mid + 1);   // positives missing before arr[mid]
        if (missing < k) lo = mid + 1;
        else hi = mid - 1;
    }
    return lo + k;                             // equivalently hi + 1 + k
}

Dry run on arr = [2, 3, 4, 7, 11], k = 5. The missing values per index are [1, 1, 1, 3, 6].

lo hi mid arr[mid] missing(mid) < 5? next
0 4 2 4 1 yes lo = 3
3 4 3 7 3 yes lo = 4
4 4 4 11 6 no hi = 3, stop

lo = 4, answer 4 + 5 = 9. Check with the formula: arr[3] + (5 - 3) = 7 + 2 = 9.

Complexity. Time O(log n). Space O(1).

Edge cases and pitfalls