The O(n) Club: First Missing Positive—That Sneaky Little Integer You Forgot

The O(n) Club: First Missing Positive—That Sneaky Little Integer You Forgot

⚡ TL;DR

Your dev lead wants the smallest missing positive integer in O(n) time and O(1) space. No HashSets. No sorting. No time for existential dread. Here’s your ticket:

// Java's in-place index party
int firstMissingPositive(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        while (nums[i] > 0 && nums[i] <= nums.length && nums[nums[i] - 1] != nums[i]) {
            int tmp = nums[nums[i] - 1];
            nums[nums[i] - 1] = nums[i];
            nums[i] = tmp;
        }
    }
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] != i + 1) return i + 1;
    }
    return nums.length + 1;
}

🧠 How Devs Usually Mess This Up

Classic rookie moves:
– Shoving everything into a HashSet or extra boolean[].
– Sorting first, wasting precious milliseconds of your CPU’s life.
– Ignoring negatives or assuming 1 is always in the list. (Spoiler: It’s not always.)
Want O(n) speed and O(1) space? You’ll need to play musical chairs with array indices. Everyone else just gets detention.

🔍 What’s Actually Going On

Picture your array as a rowdy classroom. Only values 1 to n get seats; negatives and zeros sit in the hallway. Swap each eligible kid into their correct desk—student 3 belongs at index 2, student 1 at index 0. Once the dust settles, the first empty desk (nums[i] != i+1) reveals your missing positive. If everyone’s in place, then congrats—n+1 is the answer.
It’s an in-place, index-as-hash strategy that makes interviewers gleeful and your code smugly efficient.

🛠️ PseudoCode

• Loop through the array. For each nums[i]:
• If it’s between 1 and n, and not in its “correct seat” (i.e., nums[nums[i]-1] != nums[i]): swap it to its home.
• Repeat until all valid numbers are in their slots or can’t move.
• After dances, loop again:
• The first index i where nums[i] != i+1 is your answer: i+1.
• If all numbers line up, return n+1.

💻 The Code

public int firstMissingPositive(int[] nums) {
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
            int temp = nums[nums[i] - 1];
            nums[nums[i] - 1] = nums[i];
            nums[i] = temp;
        }
    }
    for (int i = 0; i < n; i++) {
        if (nums[i] != i + 1) return i + 1;
    }
    return n + 1;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Negatives, zeros, giants: Out-of-bounds? Don’t touch them. They loaf around, harmless.
• Duplicates: Don’t let swaps loop forever—always check nums[nums[i]-1] != nums[i] before the swap.
• Missing 1? If no ‘1’, just return 1—don’t overthink it.
• Time: Each value finds its seat only once. Yes, it’s really O(n).
• Space: Use only a couple variables. No sneaky arrays, no sets.

🧠 Interviewer Brain-Tattoo

“O(1) space means no cheat sheets, a single marker, and some fancy index swapping. If you reach for a HashSet, you might as well bring your resume.”