The O(n) Club: Find All Numbers Disappeared in an Array — Now With Extra Negativity

The O(n) Club: Find All Numbers Disappeared in an Array — Now With Extra Negativity

⚡ TL;DR

Caffeine fading fast? In short: You’ve got an int array of length n; every integer is 1 to n, some may be missing, some might be duplicate party crashers. Find out which numbers stayed home. The classic brute-force uses two loops and makes your CPU weep:

// Brute force (please don't do this at home)
List<Integer> missing = new ArrayList<>();
for (int num = 1; num <= nums.length; num++) {
    boolean found = false;
    for (int n : nums) {
        if (n == num) found = true;
    }
    if (!found) missing.add(num);
}
// O(n^2) — the slow lane

🧠 How Devs Usually Mess This Up

The most common response is to throw every number into a HashSet because, hey, why not? Or they build a giant auxiliary array. The problem asks for O(1) space (besides output), but next thing you know, the recruiter sighs and recommends you for the baking department instead. Classic confusion: ‘Is negating twice dangerous?’ (Spoiler: No. This isn’t quantum physics. It’s just integers.)

🔍 What’s Actually Going On

Imagine your array is a row of desks in a retro classroom. Every kid (number) who walks in flips their own desk upside down—so original! Even if a student shows up twice, the desk only cares if it’s upside down or not—no extra flips. At roll call, you just look for desks still upright; those are your missing classmates. And nobody needed an extra seating chart.

🛠️ PseudoCode

• Loop through the array:

  for (int i = 0; i < nums.length; i++) { ... }

  Each number points to a desk (index = value – 1, because Java starts counting at zero for “fun”).

• Negate the value at that desk (index):

  int idx = Math.abs(nums[i]) - 1;
  if (nums[idx] > 0) nums[idx] = -nums[idx];

  Already upside down? No action needed. Duplicates welcome, their extra mark gets ignored.

• After the parade, check which desks stayed upright (positive):

  for (int i = 0; i < nums.length; i++) {
      if (nums[i] > 0) missing.add(i + 1);
  }

  A positive desk at position i means (i+1) never showed up. Roll call done.

💻 The Code

public List<Integer> findDisappearedNumbers(int[] nums) {
    List<Integer> missing = new ArrayList<>();
    // Mark each seen position negative
    for (int i = 0; i < nums.length; i++) {
        int idx = Math.abs(nums[i]) - 1;
        if (nums[idx] > 0) {
            nums[idx] = -nums[idx];
        }
    }
    // Anything still positive? That's a missing number
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] > 0) {
            missing.add(i + 1);
        }
    }
    return missing;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• This only works if values are in 1..n and array length is n. If someone sneaks in a 0 or a 999, may your stack traces be merciful.
• Extra space means auxiliary arrays that use O(n) space. Temp variables and your result list are fair game.
• Fear not duplicates: Negating the same index twice just leaves it negative. No infinite flips. Java stays upright.
• Performance: O(n) time, O(1) in-place space (not counting output—LeetCode’s lawyers insist that’s fine).

🧠 Interviewer Brain-Tattoo

Arrays that hold numbers from 1 to n are just itching to be used as their own presence checkers. Never pay rent for extra arrays unless the lease is in the question.