Kth Missing Positive Number

Given a strictly increasing array of positive integers and k, find the kth positive integer missing from it. arr = [2,3,4,7,11], k = 5 → 9. (LeetCode problem)

Key observation: at index i, the count of missing numbers up to arr[i] is arr[i] - (i + 1) (how far arr[i] has drifted from its “expected” value if nothing were missing).

Brute force (O(n)): walk the array, incrementing k every time the current array value is <= k (each such value “absorbs” one missing slot); once the array value exceeds k, k itself is the answer.

class Solution {
    public int findKthPositive(int[] arr, int k) {
        int missingCount = 0, lastMissing = 0;
        int index = 0;

        for (int i = 1; missingCount < k; i++) {
            if (index < arr.length && arr[index] == i) {
                index++;
            } else {
                missingCount++;
                lastMissing = i;
            }
        }

        return lastMissing;
    }
}

Optimal — binary search (O(log n)): find the largest index where missing < k, then the answer is k plus that index plus one (equivalently arr[high] + (k - missing_at_high), which simplifies to the same value).

public class KthMissingPositive {
    public static int missingK(int[] arr, int n, int k) {
        int low = 0, high = n - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            int missing = arr[mid] - (mid + 1);
            if (missing < k) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return k + high + 1; // equivalently, arr[high] + (k - (arr[high] - (high+1)))
    }
}

For arr = [2,3,4,7,11], k = 5: missing counts up to each index are 1,1,1,3,6. Binary search lands on high = 3 (where missing = 3 < 5), so the answer is 5 + 3 + 1 = 9. Time: O(log n). Space: O(1).