The O(n) Club: Kth Missing Positive Number, or Why Your Integers Keep Vanishing

⚡ TL;DR

If you want the kth missing positive integer from a sorted array, you could count each one by hand—if you hate free time. Instead, peep the math and binary search:

🧠 How Devs Usually Mess This Up

Most folks think “Oh, I’ll just count from 1 upward, skipping anything in arr.” Then they run it for k = 9001 and wonder why the recruiter stopped responding. Even if you’re faster, someone forgets that off-by-one in arr[i] - (i + 1) and ends up returning candidate #42, not #41. Bonus: Hard-coding assumes arrays always start at 1—because, sure, the world’s that clean.

🔍 What’s Actually Going On

Picture a stadium seat chart with random missing chairs, and your boss yells, “Give me the 5th missing seat number, STAT!” At position i in arr, the number of gaps before is arr[i] - (i + 1). Want the kth missing? Don’t loop with a flashlight; use binary search to jump right to the gap’s doorstep. Edge cases: If you’re missing numbers before arr[0], don’t even need the array. And if you run off the end, just add what’s left to the last arr value. Lazy, but it works.

🛠️ PseudoCode

Step 4: Else, find kth missing before arr[l]:

return arr[l - 1] + (k - (arr[l - 1] - l));

Step 3: If l == arr.length, kth missing comes past arr’s end:

return arr[arr.length - 1] + (k - (arr[arr.length - 1] - arr.length));

Step 2: Binary search for smallest index l where missings ≥ k:

int l = 0, r = arr.length - 1;
while (l <= r) {
    int m = l + (r - l) / 2;
    int missing = arr[m] - (m + 1);
    if (missing < k) l = m + 1;
    else r = m - 1;
}

Step 1: If k is less than arr[0], congrats, kth missing is just k.

if (k < arr[0]) return k;

💻 The Code

public int findKthPositive(int[] arr, int k) {
    int n = arr.length;
    if (k &lt; arr[0]) return k;
    int l = 0, r = n - 1;
    while (l &lt;= r) {
        int m = l + (r - l) / 2;
        int miss = arr[m] - (m + 1);
        if (miss &lt; k) l = m + 1;
        else r = m - 1;
    }
    if (l == n) {
        return arr[n - 1] + (k - (arr[n - 1] - n));
    }
    return arr[l - 1] + (k - (arr[l - 1] - l));
}

⚠️ Pitfalls, Traps & Runtime Smacks

Missing Before Start: If arr starts after 1, and k is tiny, don’t even read arr; kth is k. No, really.
Off-by-One Special: Forgetting one plus/minus and you’ll be off by an entire bug bounty.
Unsorted or Duplicates? Problem expects perfection. Feed it junk, get junk results.
Overshooting: If binary search runs off-the-right, just add leftovers to arr’s last. Like topping off your coffee with energy drink.
Performance: O(log n). Use brute force and lose your lunch break.