What is the brute force approach and complexity for Missing Number?

For each k in 0..n, scan the array to see if k is there with time complexity O(N²) and space complexity O(1).

What is the optimal approach and complexity for Missing Number?

Swap each value v < n into index v, park n, then find the first slot without its own value with optimal time complexity O(N) and space complexity O(1).

How do you identify the pattern for Missing Number?

Look for key signals in the prompt: "numbers in the range 0..n" indicates Every value fits an index — value v can live at index v.; "n numbers, one missing" indicates After putting everyone home, the one empty home is the answer.; "O(1) extra space" indicates No seen[] array — the input array must be the checklist..

Missing Number

Q: What is the optimal approach and complexity for Missing Number?

Swap each value v < n into index v, park n, then find the first slot without its own value with optimal time complexity O(N) and space complexity O(1).

Q: How do you identify the pattern for Missing Number?

Look for key signals in the prompt: "numbers in the range 0..n" indicates Every value fits an index — value v can live at index v.; "n numbers, one missing" indicates After putting everyone home, the one empty home is the answer.; "O(1) extra space" indicates No seen[] array — the input array must be the checklist..

Easy·LeetCode #268Basic Anchor

LeetCode

Jump:

30-Second Mental ModelCyclic Sort — missing number (home of v is index v)

Complexity:O(N²)→O(N)

Key Insight

The checklist from the better version can live inside nums. Give value v the home nums[v]. Swap every value into its home; the value n has no home, so leave it parked. After that, index i holds i exactly when i is present, and the parked n (if any) sits on the one hole.

Core Validity Invariant

Keep swapping nums[i] into its home while nums[i] < n and nums[nums[i]] != nums[i]. After that, the answer is the first i with nums[i] != i, or n if every slot is right.

Problem

You are given an array nums of n distinct numbers. Every number is taken from the range 0, 1, 2, …, n.

That range has n + 1 values but the array only has n of them, so exactly one value is left out. Return that value.

Follow-up: can you do it in O(N) time and O(1) extra space?

Input

An integer array nums of length n with distinct values in 0..n.

Output

The single value in 0..n that does not appear in nums.

Example 1

Input: nums = [3, 0, 1]

Output: 2

n = 3, so the values should be 0, 1, 2, 3. Only 2 is not there.

Example 2

Input: nums = [0, 1]

Output: 2

n = 2, so the values should be 0, 1, 2. 0 and 1 are present, so the missing one is 2 = n.

Example 3

Input: nums = [9, 6, 4, 2, 3, 5, 7, 0, 1]

Output: 8

n = 9. Every value from 0 to 9 appears except 8.

Constraints

• n == nums.length
• 1 ≤ n ≤ 10^4
• 0 ≤ nums[i] ≤ n
• All values in nums are distinct.

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
How many values could appear, and how many slots does the array have?
2.
If I had a checklist of 0..n, how would I tick it off in one pass?
3.
Is there a natural index where the value 0 could live? The value 1? The value v?
4.
Which value has no index it could live at?
5.
Once every value sits at its own index, how do I spot the hole?

Brute force approach

Idea

Try k = 0, then 1, then 2, … up to n. For each k, scan the whole array. The first k that is not found is the answer.

Thinking process

1
The question is literally: which value in 0..n is not in the array?
2
So ask it directly for each candidate: is 0 here? is 1 here? …
3
Exactly one candidate fails, so the loop always finds it by k = n.

Code & Implementation

brute.cpp

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();

        // The answer is one of 0..n, so try them in order.
        for (int k = 0; k <= n; k++) {
            bool found = false;
            for (int x : nums) {            // linear search for k
                if (x == k) { found = true; break; }
            }
            if (!found) return k;
        }
        return -1;   // never reached: exactly one of 0..n is missing
    }
};

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        for (int k = 0; k <= n; k++) {
            boolean found = false;
            for (int x : nums) {
                if (x == k) {
                    found = true;
                    break;
                }
            }
            if (!found) return k;
        }
        return -1;
    }
}

class Solution:
    def missingNumber(self, nums: list[int]) -> int:
        n = len(nums)
        for k in range(n + 1):
            found = False
            for x in nums:
                if x == k:
                    found = True
                    break
            if not found:
                return k
        return -1

export function missingNumber(nums: number[], ...args: any[]): number {
    const n = nums.length;
    for (let k = 0; k <= n; k++) {
        let found = false;
        for (const x of nums) {
            if (x === k) {
                found = true;
                break;
            }
        }
        if (!found) return k;
    }
    return -1;
}

Complexity

Time O(N²)Space O(1)

Up to n + 1 candidates, each needing a full scan of n numbers. With n = 10^4 that is about 10^8 steps — it passes here, but it does not scale.

Better approach

Why brute force is slow

Every "is k present?" is answered by scanning all n numbers again.

What repeated work are we doing?

The same array is read up to n + 1 times, once per candidate.

What information can we reuse?

Read the array once into a checklist. After that, each candidate costs O(1).

New approach

Idea

Make a vector<bool> seen(n + 1). One pass over nums sets seen[x] = true. Then the only index k with seen[k] == false is the answer.

Thinking process

1
The brute force rescans the array once for every candidate k.
2
All the candidates are small numbers 0..n, so a plain boolean array can act as a checklist.
3
Tick off every value in one pass, then look for the box that was never ticked.

Code & Implementation

better.cpp

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();

        // seen[v] is true when v appears. Values are 0..n, so n + 1 boxes.
        vector<bool> seen(n + 1, false);
        for (int x : nums) seen[x] = true;

        for (int k = 0; k <= n; k++) {
            if (!seen[k]) return k;
        }
        return -1;   // never reached
    }
};

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        boolean[] seen = new boolean[n + 1];
        for (int x : nums) seen[x] = true;
        for (int k = 0; k <= n; k++) {
            if (!seen[k]) return k;
        }
        return -1;
    }
}

class Solution:
    def missingNumber(self, nums: list[int]) -> int:
        n = len(nums)
        seen = [False] * (n + 1)
        for x in nums:
            seen[x] = True
        for k in range(n + 1):
            if not seen[k]:
                return k
        return -1

export function missingNumber(nums: number[], ...args: any[]): number {
    const n = nums.length;
    const seen = new Array(n + 1).fill(false);
    for (const x of nums) seen[x] = true;
    for (let k = 0; k <= n; k++) {
        if (!seen[k]) return k;
    }
    return -1;
}

Complexity

Time O(N)Space O(N)

Fast, but it needs an extra array of n + 1 booleans. Sorting the array and looking for the first nums[i] != i also works, in O(N log N) time.

Optimized approach

Idea

Start from brute force

The better version keeps a seen[] checklist of size n + 1 and then looks for the unticked box.

Find the repeated work

Nothing is repeated any more — the problem is the extra memory. But the values are exactly the numbers 0..n, and the array already has slots 0..n−1. So the array can be its own checklist: slot i is "ticked" when it holds the value i.

Define the state — what variables do I need?

nums[i]: After placement, nums[i] == i means "the value i is present".
i: The slot we are fixing now. We stay on i and keep swapping until nums[i] cannot be placed.
v = nums[i]: The value sitting at i. Its home is index v — unless v == n, which has no home.

Define validity

Keep swapping nums[i] into its home while nums[i] < n and nums[nums[i]] != nums[i]. After that, the answer is the first i with nums[i] != i, or n if every slot is right.

Define the transitions — when does each pointer move, and why is it safe?

nums[i] == n

leave it, move to i + 1

Index n is outside the array, so n has nowhere to go. It stays parked until the true owner of this slot (if any) swaps it away.

nums[nums[i]] == nums[i]

leave it, move to i + 1

The value is already at its home. (Values are distinct here, so this only happens when nums[i] == i.)

otherwise

swap(nums[i], nums[nums[i]]) and check nums[i] again

The value goes to its home and never moves again. The value that comes back to i may also belong somewhere, so we look at it next.

After placement

first i with nums[i] != i → return i; else return n

If i were in the array, placement would have put it at index i. If all of 0..n−1 are home, the missing value must be n.

What does the current window add to the answer?

Each swap fixes one slot permanently. The final scan reads the slots in order, and the only broken slot (holding the parked n) is the missing value.

Code & Implementation

optimal.cpp

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();

        // Value v (0..n-1) belongs at index v. Value n has no home, so it stays parked.
        for (int i = 0; i < n; i++) {
            // Keep swapping until nums[i] is n (no home) or its home already holds it.
            while (nums[i] < n && nums[i] != nums[nums[i]]) {
                swap(nums[i], nums[nums[i]]);
            }
        }

        // The first index that does not hold its own value is the missing one.
        for (int i = 0; i < n; i++) {
            if (nums[i] != i) return i;
        }
        return n;   // 0..n-1 are all home, so n is missing
    }
};

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            while (nums[i] < n && nums[i] != nums[nums[i]]) {
                int temp = nums[nums[i]];
                nums[nums[i]] = nums[i];
                nums[i] = temp;
            }
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] != i) return i;
        }
        return n;
    }
}

class Solution:
    def missingNumber(self, nums: list[int]) -> int:
        n = len(nums)
        for i in range(n):
            while nums[i] < n and nums[i] != nums[nums[i]]:
                target = nums[i]
                nums[i], nums[target] = nums[target], nums[i]
        for i in range(n):
            if nums[i] != i:
                return i
        return n

export function missingNumber(nums: number[], ...args: any[]): number {
    const n = nums.length;
    for (let i = 0; i < n; i++) {
        while (nums[i] < n && nums[i] !== nums[nums[i]]) {
            const target = nums[i];
            const temp = nums[target];
            nums[target] = nums[i];
            nums[i] = temp;
        }
    }
    for (let i = 0; i < n; i++) {
        if (nums[i] !== i) return i;
    }
    return n;
}

Complexity

Time O(N)Space O(1)

The while inside the for looks like O(N²), but every swap puts one value into its home for good, so there are at most n swaps in total.

For this problem only, there is also a math shortcut: the answer is n·(n+1)/2 − sum(nums), or the XOR of all indices 0..n and all values. Both are O(N) time, O(1) space. But they only work when exactly one value is missing and nothing repeats. Cyclic sort keeps working when there are several missing values or duplicates, which is why it is the pattern to learn here.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	For each k in 0..n, scan the array to see if k is there	O(N²)	O(1)
Better	Mark each value in a boolean array of size n + 1, then find the unmarked one	O(N)	O(N)
Optimal	Swap each value v < n into index v, park n, then find the first slot without its own value	O(N)	O(1)

Why does this belong to this pattern?

Clues in the problem statement

“numbers in the range 0..n”Every value fits an index — value v can live at index v.
“n numbers, one missing”After putting everyone home, the one empty home is the answer.
“O(1) extra space”No seen[] array — the input array must be the checklist.

Values in 0..n+find what is missing+O(1) extra space→Cyclic Sort — missing number (home of v is index v)

This is the anchor for the "missing" sub-pattern: put each value at its home, then the slot that does not hold its own value tells you what is missing. Two details are special here. The values start at 0, so the home of v is index v (not v − 1). And there is one value too many for the slots — n has no home, so the swap loop must skip it. Find All Numbers Disappeared uses values 1..n (home v − 1) and adds duplicates; First Missing Positive adds junk values that must be skipped.

Don't make this mistake

Trying to place n at index n

✗ while (nums[i] != nums[nums[i]]) // nums[i] can be n swap(nums[i], nums[nums[i]]);

✓ while (nums[i] < n && nums[i] != nums[nums[i]]) swap(nums[i], nums[nums[i]]);

This is the pattern-confusion trap for this problem. The values go up to n, but the indices only go up to n − 1. When nums[i] == n, nums[nums[i]] reads past the end of the array. The value n simply has no home — skip it and leave it parked.

Using the 1..n home rule (v − 1)

✗ while (nums[i] >= 1 && nums[nums[i] - 1] != nums[i]) swap(nums[i], nums[nums[i] - 1]); ... if (nums[i] != i + 1) return i + 1;

✓ while (nums[i] < n && nums[nums[i]] != nums[i]) swap(nums[i], nums[nums[i]]); ... if (nums[i] != i) return i;

Also pattern confusion: copying the template from First Missing Positive or Find All Numbers Disappeared, where values are 1..n and the home is v − 1. Here the values start at 0, so the home is v itself. With the wrong rule the value 0 has no home and is skipped, and the scan checks for the wrong thing: on [1, 2] every slot looks correct, so the code never reports 0, which is the real answer.

Using if instead of while

✗ if (nums[i] < n && nums[i] != nums[nums[i]]) swap(nums[i], nums[nums[i]]);

✓ while (nums[i] < n && nums[i] != nums[nums[i]]) swap(nums[i], nums[nums[i]]);

After one swap, the value that lands at i may also need to move. On [1, 2, 3, 0] the single swaps give [2, 1, 0, 3]: the 2 left behind at index 0 is never looked at again. The scan then says 0 is missing, but the answer is 4.

Forgetting the "n is missing" case

✗ for (int i = 0; i < n; i++) if (nums[i] != i) return i; return -1;

✓ for (int i = 0; i < n; i++) if (nums[i] != i) return i; return n;

On [0, 1] every slot is correct after placement. The missing value is the one with no slot at all: n = 2.

Using the sum trick on a different problem

✗ return n * (n + 1) / 2 - accumulate(nums.begin(), nums.end(), 0);

It is a nice O(1)-space answer for this problem, and fine to use in an interview here. But it only works when exactly one value is missing and none repeat. As soon as there are duplicates or several missing values (the next questions in this sub-pattern), the sum cannot tell you which ones. Learn the cyclic sort version — it carries over.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Cyclic Sort translate into production architectures and low-level memory mechanics.

LLD Architecture