Find All Numbers Disappeared in an Array

Problem Link

• LeetCode Version

Problem Statement

Given an array nums of n integers where nums[i] is in the range [1, n], return an array of all the integers in the range [1, n] that do not appear in nums.

Example 1:

Input: nums = [4,3,2,7,8,2,3,1]
Output: [5,6]

Example 2:

Input: nums = [1,1]
Output: [2]

Before Coding: Think Like a Human

Imagine someone hands you a list of numbers from 1 to n and asks :

"Are there any missing numbers here?"

A human approach:

• Glance at the list and count how many elements the array have.

• Create a missing list.

• Start from 1 and Ask — is this number in the list?.

• If not, it's missing — so add to the missing list.

• Repeat the process till we reach the end

• Return the missing list

This intuitive idea leads us to different solutions. Let's walk through them.

🧠 Whiteboard Thinking

Before writing a single line of code, let’s think on paper (It is essential to push yourself and try to implement the whiteboard thinking )

1. Understand the Problem and clarify the Input/Output

2. Edge Cases to Consider

1. Brute Force Approach

Let’s now translate your human reasoning into clean, readable code — as if you're explaining your thought process step-by-step.

function findDisappearedNumbers(nums) {
    const n = nums.length;
    const result = []
    for (let i = 1; i <= n; i++) { // Step 1: Create a loop from 1 to n
        if (!nums.includes(i)) { // Step 2: Ask — is this number in the list?
            result.push(i); // Step 3: If not, it's missing — so add to the result
        }
    }
    return result; // Step 4: Return all missing numbers
}

Time Complexity: remember how we said includes() is O(n), and we run it inside a loop of size n + 1. So total time = O(n²).
Space Complexity: Stores missing numbers. In the worst case, all numbers 1 through n could be missing → up to n elements → O(n) space.
Why not to Use: This becomes slow when the array contains thousands or millions of elements.

2. Using a Hash Set

If your first solution was brute force — that’s totally fine! Everyone starts somewhere. The important thing is knowing when to level up. Take a closer look at the brute force approach — we’re looping through the array and using.includes(), which is itself another loop. That’s two loops! The goal now is to cut down that time. So, how do we avoid using .includes()?

Let’s shift our mindset. We’re in search mode, so we’re looking for a missing number. Enter the Hash Set: a powerful data structure that stores unique values and gives you lightning-fast lookups, insertions, and deletions—all in constant time (O(1)).

Think of a Hash Set like a magic locker system. Instead of checking every single locker (like .includes() you do), you get the exact locker number using a hash function. No wandering. No searching. Just a direct hit.

So let’s switch it up: use a Set, toss all the numbers into it, and then check for the missing number with set.has(i) — no more nested loops. It’s a constant-time lookup in the hash set.

function findDisappearedNumbers(nums){
    const newSet = new Set(nums) //Creating the Set: O(n)
    const result = [] //Space Complexity: O(n) – due to storing all values in a set.
    for(let i = 1; i <= nums.length; i++){ // Looping from 1 to n: O(n)
        if(!newSet.has(i){  //Set lookup is O(1) on average
            result.push[i]
        }
    }
}

Time Complexity: is O(n) overall: creating the Set takes O(n) time, looping from 1 to n takes O(n) time, and each Set lookup is O(1) on average.
Space Complexity: O(n) We store all elements in a Set which takes extra space
Why not to Use: Now don’t get me wrong — switching from brute force to a Hash Set is a solid upgrade. But if we’re aiming for the cleanest, most efficient solution, we can still do better without the need of extra space.

3. Cyclic Sort Version (Interview Pattern)

So here’s something cool — the original Cycle Sort was invented way back in 1963 by a guy named W. D. Jones. His whole mission? Create a sorting algorithm that used the fewest possible writes. Why? Because back in the day, memory was limited and hardware was kind of fragile, so minimizing writes wasn’t just a nice-to-have — it was essential.

Fast forward to today, and we’ve got what’s often called Cyclic Sort in coding interviews. It's not exactly the same, but it’s based on the same idea — do less, but do it smart. And instead of worrying about hardware, now it’s all about solving problems efficiently under pressure.

So what’s the difference?

• Cycle Sort (1963): For each element, it looks around and figures out its exact place by comparing it with others.

• Cyclic Sort (Interview Version): It just places each number directly where it belongs using swaps — quick, in-place, and done in one pass.

We’re not diving deep into the history or theory here, but if you want to explore more, [here’s a link].

Let’s visualize this.

You’re on a plane, and each passenger is holding a ticket numbered from 1 to n. But there’s a mix-up. Some passengers are in the wrong seats, some seats are empty, and some numbers are even duplicated.

Now, your job? Find out which seat numbers are missing — without checking every single seat one by one.

Here’s how we can apply the smart swaps strategy to solve this:

1. Step 1: Start with the first person.
   Let i = 0. If the person in seat i is not holding ticket i + 1, swap them with the person who is.

   Step 2: Continue this process for every seat.
   You’re placing each number at its correct index: if num = 4, it should be at index 3.

   Step 3: After the swaps, the seats that were never correctly filled? Those are your missing numbers.

The beauty here is: each element only moves once to its correct spot — no repeated scans.

Now let’s try to implement it. We will understand every line and come to us as natural as brute force solutions. This is nothing new to you; it’s something you know, but you will be connecting it differently

What you know:

• To create a function

• We know we have to start from the first element, hence let i = 0;

• We know we have to have a loop for every element, while (i < nums.length){}.

• From the question, we know integers are in the range [1, n].

• Remember, arrays start at index 0 — so if a number is 1, it belongs at index 0. if 2 should be at index 1, a 3 at index 2, and so on. Basically, for any number n, its correct index is n - 1

• So it’s safe to create const correctIndex = nums[i] - 1

    let nums = [4, 3, 2, 7, 8, 2, 3, 1];
    i = 0 // nums[0]= 4 
    correctIndex = nums[i]-1 // 4-1= 3 (because 4 belongs at index 3)
    //we should right an if statment the vaule in nums !== the correct index we should swap
    if(nums[i] !== nums[correctIndex])
  

• Now it’s time for swapping, just to refresh your memory in destructuring style

• Swapping time, we know to swap when: The current number is not already at its correct index, and we’re not swapping a duplicate

    let arr = [1, 3, 2, 4]; // Swap the values at index 1 and index 2
    [arr[1], arr[2]] = [arr[2], arr[1]]; //arr[1] is 2  & arr[2] is 3
    console.log(arr); // Output: [1, 2, 3, 4]
  

• If they are duplicates or in place, we move on to the next i++

• After rearrangement, we will have a beautiful list ,Now you are aware we have duplicates and missing values

    let nums = [5, 3, 3, 2, 1] //i = 0; nums[0] with nums[nums[0]-1 ] which is nums[4]
    nums = [1, 3, 3, 2, 5]//i = 1; nums[1] with nums[2] //skip duplicate
    nums = [1, 3, 3, 2, 5]//i = 2; nums[2] with nums[2] //skip duplicate
    nums = [1, 2, 3, 3, 5]//i = 3; nums[3] with nums[1] 
    nums = [1, 2, 3, 3, 5]//i = 4; nums[4] with nums[4] //skip already correct
    //Move to i = 5 (done) nums = [1, 2, 3, 3, 5]
  

  This isn’t something new — it’s something you already know. You’re just connecting the dots in a smarter way. If you've followed along this far and absorbed it, my hat’s off to you.

  Now grab a piece of paper and try walking through an example on your own. That’s how a student becomes a master. 🎓

  We now have a beautifully rearranged list. The next step? Let’s find the missing numbers.

  Think about how a consecutive sequence works: each number should be exactly one more than the index it sits on — meaning i + 1. So if at any index i, the value isn’t i + 1, that number is missing from the array.

  Here’s how we can implement that:

  • Loop through the array.

  • Use our condition statement which is if (nums[i] !== i+1) meaning missing number alert

  • If it’s not, that means i + 1 is missing — so we push it to our result array.

  • At the end, return the result array.

Let’s bring it home with the full function:

function findDisappearedNumbers(nums) {
  let i = 0;
  while (i < nums.length) {
    const correctIndex = nums[i] - 1;
    // Only swap if the target isn't already in place
    // and we’re not swapping a duplicate
    if (nums[i] !== nums[correctIndex]) {
      [nums[i], nums[correctIndex]] = [nums[correctIndex], nums[i]];
    } else {
      i++;
    }
  }
  const result = [];
  // After rearrangement, if nums[i] !== i + 1, then (i + 1) is missing
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] !== i + 1) {
      result.push(i + 1);
    }
  }
  return result;
}

Time Complexity O(n) — linear time

• First pass (while loop): In the worst case, every element could be swapped once to its correct position. But thanks to the condition nums[i] !== nums[correctIndex], each element is moved only when necessary and never more than once. So, this loop runs in O(n).

• Second pass (for loop): A single loop through the array to collect missing elements — also O(n).

👉 Overall time complexity:O(n) + O(n) = O(n)

Space Complexity

O(1) — constant space (ignoring output)

• The sorting is done in-place, with only a few variables used.

• The only extra space is the result array, which at most holds n elements (in the worst case, all numbers from 1 to n are missing). Since this is required output, we don’t count it toward space complexity.

👉 Overall space complexity (excluding output): O(1)

4. Negative Marking Approach (Interview Pattern)

I’ve got another in-place trick for you — because the more, the merrier, right? This one's a bit different from our usual cyclic sort. But don’t worry, we walk with it together, plus you know your girl is a visualizer — if I can’t see it, I can’t visualize it. Like going to a restaurant with no menu pictures and someone orders the Tunna Krispy. What even is that? Sounds like a Pokémon evolution of a fish stick.Anyway — back to the point.

Let’s visualize Think of It Like Playing Cards

Imagine you’re handed a messy deck of cards with numbers ranging from 1 to n. But this deck? It’s chaotic. Some cards are missing, and others are duplicated. These cards represent your nums array. Your mission is to win the game by figuring out which numbers are missing so you can rebuild the perfect sequence from 1 to n. Here’s the twist — you can only view each card once. No sorting, no extra space, just quick thinking and sharp memory. If you’ve got photogenic memory, please share — the rest of us are barely surviving out here.

♠️ Strategy: Flip It, Mark It

Here’s how you play smart:

• When you see a card with number x, you flip the card at index x - 1.

• Why? Because that marks: “Hey, I’ve seen the number x.”

• If that index is already flipped (i.e., in computer style, make it negative)?
  Cool, that means we’ve seen a duplicate — just leave it.

So imagine this:
You see a 1 → go to the 1st position in the deck → flip it face-down.
You see a 2 → go to the 2nd position → flip it.
You see another 2 later? That 2nd card’s already flipped → skip.

You keep flipping cards based on what number they say they are.
You don’t touch the cards themselves — you just use them to flip others.

Once you’ve gone through the whole deck (your array):

• The flipped cards are the ones you've “seen”.

• The cards still face-up (i.e., positive) at index i?
  That means the number i + 1 was never seen — that’s your missing number.

That’s how you figure out what numbers are missing in one pass and with no extra space.

Now let’s try to implement it. As usual lets start with what we know , you always know more than you think.

• We know how to create a loop to go over the array

• We know that JavaScript index system and the range we explained it earlier nums[i] - 1

• Remember how we said we flipped but technically we have to convert it negative value.

• We want each number to make the value as its matching position negative It's the core trick that makes this whole algorithm in-place and reliable — and ensures duplicates don’t mess things up.

  That’s where Math.abs(nums[i]) comes in — it gives us the absolute value, ignoring the negative sign if it’s there.

  •   let nums = [4, 3, 2, 7, 8, 2, 3, 1];
      // Step-by-step walkthrough using the negative marking strategy
    
      // i = 0; nums[0] = 4 => index = 3
      // Flip nums[3] = 7 => mark as seen by making it negative
      nums = [4, 3, 2, -7, 8, 2, 3, 1];
    
      // i = 1; nums[1] = 3 => index = 2
      // Flip nums[2] = 2 => mark as seen by making it negative
      nums = [4, 3, -2, -7, 8, 2, 3, 1];
    
      // i = 2; nums[2] = -2 => Math.abs(-2) = 2 => index = 1
      // Flip nums[1] = 3 => mark as seen by making it negative
      nums = [4, -3, -2, -7, 8, 2, 3, 1];
    
      // i = 3; nums[3] = -7 => Math.abs(-7) = 7 => index = 6
      // Flip nums[6] = 3 => mark as seen by making it negative
      nums = [4, -3, -2, -7, 8, 2, -3, 1];
    
      // i = 4; nums[4] = 8 => index = 7
      // Flip nums[7] = 1 => mark as seen by making it negative
      nums = [4, -3, -2, -7, 8, 2, -3, -1];
    
      // i = 5; nums[5] = 2 => index = 1
      // nums[1] is already negative => skip (we’ve seen 2 already) and so on .
    

• Now we have arranged list we can simply create a empty array and push the value that stayed positive means the number spot is missing

  Let’s bring it home with the full function:

    function findDisappearedNumbers(nums) {
      for (let i = 0; i < nums.length; i++) {
        const index = Math.abs(nums[i]) - 1;
        if (nums[index] > 0) {
          nums[index] = -nums[index]; // flip it to mark as seen
        }
      }
      const result = [];
      for (let i = 0; i < nums.length; i++) {
        if (nums[i] > 0) {
          result.push(i + 1); // index + 1 was never seen
        }
      }
      return result;
    }
  

Similarly to Cyclic Sort Approach the time complexity is O(n) and space complexity is O(1) .

When to Use Which?

• Use negative marking if:

  • Simpler, cleaner code is preferred.

  • You're allowed to negate the input array.

• Use cyclic sort if:

  • You need to preserve all positive values.

  • You want to generalize the logic for other cyclic-sort problems (e.g., finding duplicates, first missing positive, etc.).

And just like that, with a single loop and a bit of sign-flipping sorcery, we’ve tracked down the missing cards. No extra memory, no double loops — just smart indexing. Try tweaking the deck and running it again. Better yet, try explaining it to a friend — that’s when you know you’ve mastered it."

Final Thoughts

Finding all the missing numbers in an array might sound like a routine task, but it’s a surprisingly rich opportunity to flex your problem-solving muscles. We started with the basics — brute force, the “check everything” method. Then we leveled up with a HashSet to track seen numbers more efficiently.

But the real magic came with the Cyclic Sort approach and the in-place negative marking trick — clever strategies that solve the problem in a single pass, with no extra space and linear time. Just flip the values at the right spots and let the array itself do the talking. It’s elegant, memory-efficient, and honestly, pretty satisfying to implement.

The Big Lesson?

Sometimes, solving a problem isn’t about brute force or complex data structures. It’s about seeing the pattern, trusting the process, and flipping the script (or the card 😉). Keep collecting these mental models, and you’ll start to recognize the rhythm behind the chaos, one problem at a time.