What is the brute force approach and complexity for Set Mismatch?

For each k in 1..n, scan the array and count how often k appears with time complexity O(N²) and space complexity O(1).

What is the optimal approach and complexity for Set Mismatch?

Swap each value v into index v − 1; the one wrong slot gives both answers with optimal time complexity O(N) and space complexity O(1).

How do you identify the pattern for Set Mismatch?

Look for key signals in the prompt: "numbers 1 to n" indicates Each value v has a natural home: index v − 1.; "one number repeated" indicates One value finds its home already occupied by its twin.; "one number missing" indicates One home never receives its owner.; "return both" indicates The same wrong slot shows both: the value in it is the duplicate, its index + 1 is the missing value..

Set Mismatch

Easy·LeetCode #645Basic Anchor

LeetCode

Jump:

30-Second Mental ModelCyclic Sort (missing + duplicate together)

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

Key Insight

Give value v the home nums[v − 1] and swap every value home. Every value that exists reaches its home, except the second copy of the duplicate — its home is already taken. It gets left in the only free slot, which is the home of the missing value. So the one slot i with nums[i] != i + 1 holds the duplicate, and i + 1 is the missing value.

Core Validity Invariant

Keep swapping while nums[i] != nums[nums[i] − 1] (the home of nums[i] does not already hold it). Afterwards, the only i with nums[i] != i + 1 gives duplicate = nums[i] and missing = i + 1.

Problem

An array nums of length n was supposed to hold every number from 1 to n exactly once. By mistake, one number got copied over another one. So now one value appears twice and one value is missing.

Return both of them as [duplicate, missing] — the repeated value first, then the missing value.

Input

An integer array nums of length n, with values in 1..n.

Output

An array of two numbers: [duplicate, missing].

Example 1

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

Output: [2, 3]

2 shows up twice and 3 never shows up.

Example 2

Input: nums = [1, 1]

Output: [1, 2]

1 is repeated, so 2 is missing.

Constraints

• 2 ≤ nums.length ≤ 10^4
• 1 ≤ nums[i] ≤ 10^4
• Exactly one value is repeated and exactly one value in 1..n is missing.

First, think yourself

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

1.
The values should be exactly 1..n. How many of them can I check directly, one by one?
2.
If I could use extra memory, what would tell me "how many times does k appear?" quickly?
3.
The array has n slots and the values are 1..n. Is there a natural slot for each value?
4.
If every value moves into its own slot, what would the slot of the missing value end up holding?
5.
The answer wants two numbers. Which one comes first?

Brute force approach

Idea

Go through k = 1, 2, …, n. For each k, scan the whole array and count it. A count of 2 means k is the duplicate. A count of 0 means k is missing.

Thinking process

1
The problem is really two questions: which value appears twice, and which appears zero times?
2
The simplest way to know how often k appears is to count it.
3
Do that for every k from 1 to n and remember the two special ones.

Code & Implementation

brute.cpp

class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        int n = nums.size();
        int duplicate = -1, missing = -1;

        // For every value k that should be there, count how often it appears.
        for (int k = 1; k <= n; k++) {
            int count = 0;
            for (int x : nums) {
                if (x == k) count++;
            }
            if (count == 2) duplicate = k;   // seen twice
            if (count == 0) missing = k;     // never seen
        }
        return {duplicate, missing};         // duplicate first, then missing
    }
};

class Solution {
    public int[] findErrorNums(int[] nums) {
        int n = nums.length;
        int duplicate = -1, missing = -1;
        for (int k = 1; k <= n; k++) {
            int count = 0;
            for (int x : nums) {
                if (x == k) count++;
            }
            if (count == 2) duplicate = k;
            if (count == 0) missing = k;
        }
        return new int[]{duplicate, missing};
    }
}

class Solution:
    def findErrorNums(self, nums: list[int]) -> list[int]:
        n = len(nums)
        duplicate, missing = -1, -1
        for k in range(1, n + 1):
            count = 0
            for x in nums:
                if x == k:
                    count += 1
            if count == 2:
                duplicate = k
            if count == 0:
                missing = k
        return [duplicate, missing]

export function findErrorNums(nums: number[], ...args: any[]): number[] {
    const n = nums.length;
    let duplicate = -1, missing = -1;
    for (let k = 1; k <= n; k++) {
        let count = 0;
        for (const x of nums) {
            if (x === k) count++;
        }
        if (count === 2) duplicate = k;
        if (count === 0) missing = k;
    }
    return [duplicate, missing];
}

Complexity

Time O(N²)Space O(1)

n values of k, each needing a full scan of n elements. With n = 10^4 that is 10^8 steps — slow, but it shows exactly what we are looking for.

Better approach

Why brute force is slow

Every "how many times does k appear?" is answered by scanning all n numbers again.

What repeated work are we doing?

The same array is read n times, once per k.

What information can we reuse?

Read the array once and store every count. Then each k is one lookup.

New approach

Idea

Make count[v] for v = 1..n and fill it in one pass. Then the value with count 2 is the duplicate and the value with count 0 is missing.

Thinking process

1
Brute force reads the whole array again for every k.
2
The values are small (1..n), so a plain array can be the counter — no hash map needed.
3
One pass to count, one pass to read the counts.

Code & Implementation

better.cpp

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

        // count[v] = how many times v appears. Values are 1..n.
        vector<int> count(n + 1, 0);
        for (int x : nums) count[x]++;

        int duplicate = -1, missing = -1;
        for (int k = 1; k <= n; k++) {
            if (count[k] == 2) duplicate = k;
            if (count[k] == 0) missing = k;
        }
        return {duplicate, missing};
    }
};

class Solution {
    public int[] findErrorNums(int[] nums) {
        int n = nums.length;
        int[] count = new int[n + 1];
        for (int x : nums) count[x]++;
        int duplicate = -1, missing = -1;
        for (int k = 1; k <= n; k++) {
            if (count[k] == 2) duplicate = k;
            if (count[k] == 0) missing = k;
        }
        return new int[]{duplicate, missing};
    }
}

class Solution:
    def findErrorNums(self, nums: list[int]) -> list[int]:
        n = len(nums)
        count = [0] * (n + 1)
        for x in nums:
            count[x] += 1
        duplicate, missing = -1, -1
        for k in range(1, n + 1):
            if count[k] == 2:
                duplicate = k
            elif count[k] == 0:
                missing = k
        return [duplicate, missing]

export function findErrorNums(nums: number[], ...args: any[]): number[] {
    const n = nums.length;
    const count = new Array(n + 1).fill(0);
    for (const x of nums) count[x]++;
    let duplicate = -1, missing = -1;
    for (let k = 1; k <= n; k++) {
        if (count[k] === 2) duplicate = k;
        if (count[k] === 0) missing = k;
    }
    return [duplicate, missing];
}

Complexity

Time O(N)Space O(N)

Fast, and a fine answer in an interview. But the count array uses n + 1 extra ints. The values fit the indices so well that the input array can do the counting job itself.

Optimized approach

Idea

Start from brute force

The better version counts every value in a separate count array of size n + 1 and then looks for the counts 2 and 0.

Find the repeated work

Nothing is repeated any more — the cost is the extra memory. But the counts are only needed for values 1..n, and the array has exactly n slots. If each value sits in its own slot, the slot itself says "present", and the one slot that cannot be filled says "missing".

Define the state — what variables do I need?

nums[i]: After placement, nums[i] == i + 1 means "value i + 1 is present".
i: The slot we are fixing now. We keep swapping until the value at i cannot move.
v = nums[i]: The value sitting at i. Its home is index v − 1.

Define validity

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

nums[nums[i] − 1] != nums[i]

swap(nums[i], nums[nums[i] − 1]) and look at nums[i] again

The value goes home and stays there. The value that comes back to i may also need to move.

nums[i] is already home (nums[i] == i + 1)

move to i + 1

This slot is done.

nums[i] is not home, but its home already holds the same value

leave it, move to i + 1

This is the second copy of the duplicate. Its twin owns the home, so swapping would change nothing and loop forever.

After placement

find the i with nums[i] != i + 1 → return {nums[i], i + 1}

If i + 1 were present, placement would have put it at i. It is not, so i + 1 is missing — and the value stuck there can only be the extra copy.

What does the current window add to the answer?

Each swap fixes one slot for good. In the final scan, n − 1 slots are correct and exactly one is wrong. That one slot hands us both answers.

Code & Implementation

optimal.cpp

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

        // Cyclic sort: value v belongs at index v - 1.
        for (int i = 0; i < n; i++) {
            // Stop when the home of nums[i] already holds that value.
            // For the duplicate, its home is taken by its twin, so we stop too.
            while (nums[i] != nums[nums[i] - 1]) {
                swap(nums[i], nums[nums[i] - 1]);
            }
        }

        // Exactly one slot is wrong: it holds the duplicate,
        // and its own value (i + 1) is the one that is missing.
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) return {nums[i], i + 1};
        }
        return {-1, -1};   // never reached for valid input
    }
};

class Solution {
    public int[] findErrorNums(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            while (nums[i] != nums[nums[i] - 1]) {
                int target = nums[i] - 1;
                int temp = nums[target];
                nums[target] = nums[i];
                nums[i] = temp;
            }
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return new int[]{nums[i], i + 1};
            }
        }
        return new int[]{-1, -1};
    }
}

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

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

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 fewer than n swaps in total. The array is rearranged in place.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	For each k in 1..n, scan the array and count how often k appears	O(N²)	O(1)
Better	Count every value once in an array of size n + 1	O(N)	O(N)
Optimal	Swap each value v into index v − 1; the one wrong slot gives both answers	O(N)	O(1)

Why does this belong to this pattern?

Clues in the problem statement

“numbers 1 to n”Each value v has a natural home: index v − 1.
“one number repeated”One value finds its home already occupied by its twin.
“one number missing”One home never receives its owner.
“return both”The same wrong slot shows both: the value in it is the duplicate, its index + 1 is the missing value.

Values 1..n in n slots+one duplicate+one missing→Cyclic Sort (missing + duplicate together)

In the missing sub-pattern we only read the index of the wrong slot. In the duplicate sub-pattern we only read the value in it. Here the two meet: one value appears twice and one is missing, so the single wrong slot gives both — its value is the duplicate and its index + 1 is the missing number.

Don't make this mistake

Returning the answer in the wrong order

✗ return {i + 1, nums[i]}; // [missing, duplicate]

✓ return {nums[i], i + 1}; // [duplicate, missing]

This is the pattern-confusion trap. In the missing sub-pattern the index (i + 1) is the answer, so it is easy to put it first. Here the problem wants the duplicate first. On [1, 2, 2, 4] the wrong order returns [3, 2] instead of [2, 3].

Infinite loop: checking the slot instead of the home

✗ while (nums[i] != i + 1) swap(nums[i], nums[nums[i] - 1]);

✓ while (nums[i] != nums[nums[i] - 1]) swap(nums[i], nums[nums[i] - 1]);

This condition works when every value is distinct, but here one value is doubled. On [1, 1], at i = 1 the value 1 is not at index 1, so it is swapped with index 0 — which also holds 1. Nothing changes and the loop never ends. Asking "does the home already hold this value?" stops the duplicate.

Using if instead of while

✗ if (nums[i] != nums[nums[i] - 1]) swap(nums[i], nums[nums[i] - 1]);

✓ while (nums[i] != nums[nums[i] - 1]) swap(nums[i], nums[nums[i] - 1]);

After one swap, the value that lands at i may also need to move. With if, it can stay out of place. On [4, 3, 2, 7, 8, 2, 6, 1] the if version ends as [7, 2, 3, 4, 1, 6, 2, 8] with three wrong slots, and returns [7, 1] instead of [2, 5].

Finding the duplicate with a set but guessing the missing value

✗ // found dup with a set, then: missing = dup + 1;

✓ // after placement: if (nums[i] != i + 1) return {nums[i], i + 1};

The missing value has nothing to do with the duplicate's value. In [3, 2, 3, 4, 6, 5] the duplicate is 3 and the missing value is 1.

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