1539.kth-missing-positive-number.md

1539. Kth Missing Positive Number

Brute Force

We just iterate all possible positive numbers and increment the missing count if the number is not in the array.

    fun findKthPositive(arr: IntArray, k: Int): Int {
        val set = arr.toSet()
        var missing = 0
        for (i in 1..10000) {
            if (i !in set) {
                missing++
            }
            if (missing == k) return i
        }
        return -1
    }

• Time Complexity: O(U), where U is the upper bound of the missing number.
• Space Complexity: O(n)

Binary Search

Given a sorted array arr of distinct positive integers, and a number k, we want to find the k-th missing positive integer from the sequence 1, 2, 3, ....

Key Insights

The expected value at index i (0-based) should be i + 1, because the array is supported to have 1, 2, 3, ... as its elements.

But the actual value at index i is arr[i]. So the number of missing numbers at index i is arr[i] - (i + 1). The expected value should have increased by 1 each step, but instead they increased faster, so some numbers are skipped (missing).

actual   = [2, 3, 5]
expected =  1, 2, 3
           +1           // Missing 1
              +1        // Missing 1
                 +2     // Missing 1, 4
        

We can binary search the first index i such that arr[i] - (i + 1) >= k. Then the answer is i + k, because:

• i numbers are aleady in arr.
• The missing count is k at index i.

So the k-th missing number is just before arr[i], which means i + k.

But what if we don't find such an index i?

This is the case all numbers in arr are correct, it means the k-th missing number is after the entire array, such as [1, 2, 3]. In our binary search, left will stop at arr.size, and left + k will be the answer.

fun findKthPositive(arr: IntArray, k: Int): Int {
    var left = 0
    var right = arr.size - 1
    while (left <= right) {
        val middle = left + (right - left) / 2
        val missingCount = arr[middle] - (middle + 1)
        if (missingCount >= k) {
            right = middle - 1
        } else {
            left = middle + 1
        }
    }
    return left + k
}

• Time Complexity: O(log n)
• Space Complexity: O(1)