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

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:

// Pure brute force, best paired with a strong coffee:
int miss = 0, num = 1, i = 0;
while (miss < k) {
    if (i < arr.length && arr[i] == num) i++;
    else miss++;
    num++;
}
return num - 1; // Slow and steady loses the interview

🧠 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 1: If k is less than arr[0], congrats, kth missing is just k.

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

• 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 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 4: Else, find kth missing before arr[l]:

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

💻 The Code

public int findKthPositive(int[] arr, int k) {
    int n = arr.length;
    if (k < arr[0]) return k;
    int l = 0, r = n - 1;
    while (l <= r) {
        int m = l + (r - l) / 2;
        int miss = arr[m] - (m + 1);
        if (miss < 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.

🧠 Interviewer Brain-Tattoo

“Gaps in your array don’t go away if you ignore them. But with math and binary search, at least you won’t waste a lifetime finding them.”