Missing Number

Problem Link

• LeetCode Version

Problem Statement

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Example 1:

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

Example 2:

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

Before Coding: Think Like a Human

Imagine someone hands you a list of numbers from 0 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.

• Start from 0 — is it there?, what about 1?

• If yes, continue to the consecutive number.

• Repeat the process till we find the missing number.

• Return the missing number

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:

1. Understand the Problem and clarify the Input/Output

   • Input: An array of n distinct integers in the range [0, n].

   • Output: The single number in that range that’s missing from the array.

2. Edge Cases to Consider

   • Empty array ([]) → Should return 0.

   • Array with full range except the last number → [0,1,2,3] missing 4.

   • Array with one number → [1] → missing 0.

1. Brute Force Approach

Let’s start with the most straightforward method: brute force.

Think of brute force as trying every possibility without using any cleverness or optimization.

Imagine you're organizing chairs for a group photo. You’ve labeled the spots from 0 to n, and everyone takes a seat — but one chair is left empty.

To find the missing number, you’d probably start from 0 and check:
"Is someone sitting here? Yes. What about seat 1? Okay, taken."
You’d keep going until — bam — you spot the empty seat.

Even to a human, this would require a lot of effort. Now imagine doing this with millions of people—or millions of integers. In programming, this is what brute force looks like.

function missingNumber(nums){
  const n = nums.length;
  for (let i = 0; i <= n; i++) { //this is a loop
    if (!nums.includes(i)) {  // includes() is O(n) inside a loop.
      return i;
    }
  }
}

Time Complexity: includes() is O(n), and we run it inside a loop of size n + 1. So total time = O(n²).
Space Complexity: O(1) (constant space).we don’t use any extra 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 right hence 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.

What Does “Constant-Time Operation or lookup” Mean?

When we say an operation is constant time (written as O(1)), we mean:

It takes the same amount of time no matter how big the input is.

So for set.has(i):

• Whether your set has 10 elements or 10 million, checking set.has(i) will still take the same amount of time (on average).

• It does not loop through the elements — it jumps directly to the value’s “slot” using hashing.

function missingNumber(nums){
  const n = nums.length;
  const newSet = new Set(nums)
  for (let i = 0; i <= n; i++) { //this is a loop
    if (!newSet.has(i)) {  
      return i;
    }
  }
}

Time Complexity: O(n) loop × O(1) lookup = O(n) total time
Space Complexity: O(n) – due to storing all values in a set.
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.

Here’s why:

• Extra Space: Even though lookups are fast, we’re creating a whole new Set to store the numbers. That’s extra memory we’re using — O(n) space.

• We Can Solve It Without Extra Storage: The problem is asking us to find one missing number. And we already have all the info we need in the array and the range [0, n]. So do we really need another data structure just to spot the gap?

• There's a Math Trick: With a bit of clever math (spoiler alert: Gauss knew this over 200 years ago), we can solve this in one pass, constant space, and blazing speed — without any Set or extra memory at all.

So while Hash Set is a nice step up, it’s not the final form. If you want sleek and efficient, the math-based approach is where the magic happens.

3. Best Approach — Gauss’ Formula

What if I told you we could find the missing number without any loops inside loops, without creating a Set, and using just a pinch of math?

So here’s the trick:

• Calculate what the sum should be using the formula → expectedSum

• Add up all the numbers in your array → actualSum

• The missing number is just the difference:

History Time 🧮 This idea actually goes back to Carl Friedrich Gauss, a mathematician who figured this out as a kid (yep, a kid). It goes back to a story about young Gauss in school. His teacher told the class to add the numbers from 1 to 100 (probably hoping it’d keep them busy for a while). But Gauss noticed a pattern. He realized that if you have all the numbers from 0 to n, the sum of those numbers can be calculated with a simple formula:

Expected Sum = n * (n + 1) / 2

What Does (n * (n + 1)) / 2 Do?

This formula calculates the sum of all numbers from 0 to n (inclusive).Let’s take an example:

Suppose n = 4
That means we expect the numbers: [0, 1, 2, 3, 4]
Now use the formula:

expectedSum = (n*(n+1))/2
(4 * (4 + 1)) / 2 = (4 * 5) / 2 = 20 / 2 = 10
//The sum should be: 0 + 1 + 2 + 3 + 4 = 10

So now we figured out expectedSum , next step is actualSum , how can we not use a loop and get the actual sum from 0 to n . Try to think of which method will help you. .reduce() is a built-in array method that processes each element in the array and reduces it to a single value — in this case, the sum.

const actualSum = nums.reduce((acc, num) => acc + num, 0);

Here’s how it works in this line:

• acc is the accumulator — it keeps track of the running total.

• num is the current element in the array.

• 0 is the initial value of the accumulator (i.e. we start summing from 0).

function missingNumber(nums: number[]): number {
  const n = nums.length;
  const expectedSum = (n * (n + 1)) / 2;
  const actualSum = nums.reduce((acc, num)=> acc +num , 0 )
  return expectedSum - actualSum
}

Time Complexity: O(n)
Space Complexity: O(1) — no extra space needed, just two numbers!
Why not to Use: Honestly? No reason — unless you totally forgot this formula exists (hey, it happens). In that case, welcome back to middle school math class!

Final Thoughts

Finding the missing number might feel like a simple task, but it’s a great playground for thinking like a problem solver. We started with brute force , leveled up with Hash Set and then Finally, you unlocked the math trick — the slickest solution of them all. It’s just one formula and a single pass. No loops inside loops. No extra memory. Just math doing its thing.

The Big Lesson?

Sometimes the best solution isn’t about writing more code — it’s about stepping back, spotting the pattern, and writing smarter code.

So next time you're solving a problem, start however you can — then keep optimizing until it clicks. That’s the real glow-up.