Set Mismatch (LC 645)

Pattern: Cyclic Sort (and related in-place marking)
Difficulty: Easy
Key Concept: Numbers should be 1..n at indices 0..n-1; after placing each x at index x-1, the first slot where nums[i] != i+1 reveals the duplicate (the value stuck there) and missing (i+1).

Problem Statement

You have an array nums of length n that was supposed to be a permutation of 1, 2, …, n, but one number was duplicated and one number from 1..n is missing.

Return a two-element array: [duplicate, missing].

Input: int[] nums of length n, exactly one duplicate and one missing in 1..n.
Output: int[] of length 2 — first the duplicated value, then the missing value.

Example: nums = [1, 2, 2, 4] → [2, 3] (should be 1,2,3,4; 2 appears twice, 3 is absent).

---

1. Algorithm & Pseudocode

Brute force A — sort then scan

sort nums
for i from 0 to n-2:
    if nums[i] == nums[i+1]:
        duplicate = nums[i]
        break
for k from 1 to n:
    if k not in nums (linear scan or binary search on sorted array):
        missing = k
return [duplicate, missing]

Brute force B — HashSet

seen = empty set
duplicate = -1
for each x in nums:
    if x in seen: duplicate = x
    else add x to seen
for k from 1 to n:
    if k not in seen: missing = k
return [duplicate, missing]

Optimal — cyclic sort

i = 0
while i < n:
    correctIndex = nums[i] - 1
    if nums[i] != nums[correctIndex]:
        swap nums[i], nums[correctIndex]
    else
        i++

for i from 0 to n-1:
    if nums[i] != i + 1:
        return [nums[i], i + 1]
return null // unreachable with valid input

Interpretation: At the first mismatch, the value at nums[i] is the extra copy (duplicate); the value that should be there is i+1 (missing).

---

2. Step-by-Step Analysis (Beginner-Friendly)

Why sorting works: Duplicates become adjacent; the missing number is found by comparing expected 1..n to what you see. Downside: O(n log n) time.

Why HashSet works: You detect the duplicate when inserting a value twice; the missing integer is the one in 1..n never inserted. Downside: O(n) extra space.

Why cyclic sort is the cleanest for this family: Values are exactly 1..n, so index nums[i]-1 is always valid. Swapping puts each number in its “correct” cell. When a duplicate blocks progress (nums[i] == nums[correctIndex] but the array still wrong globally), you advance i; after the pass, the wrong slot encodes both answers.

Negative marking is also possible (mark presence at nums[val-1]), but cyclic sort matches the pattern guide and is easy to justify in one scan after swaps.

---

3. The Dry Run

Sample: nums = [1, 2, 2, 4], n = 4. Expected: duplicate 2, missing 3.

Cyclic sort trace

Step	i	Array	nums[i]	correctIndex	Action
0	0	[1,2,2,4]	1	0	Already matches nums[0] vs nums[0] → i++
1	1	[1,2,2,4]	2	1	Same → i++
2	2	[1,2,2,4]	2	1	nums[2] equals nums[1] (both 2) → i++
3	3	[1,2,2,4]	4	3	Same → i++
end	—	[1,2,2,4]	—	—	Final verification loop

Final scan (expect nums[i] == i+1):

Index i	nums[i]	Expected i+1	Match?
0	1	1	Yes
1	2	2	Yes
2	2	3	No → duplicate = nums[2] = 2, missing = 3
3	4	4	Yes

Return [2, 3].

---

4. Java Solution

Brute Force

Sort + scan — Time: O(n log n), Space: O(1) if sorting in-place (ignoring sort stack for Arrays.sort on primitives).

import java.util.*;

class Solution {
    public int[] findErrorNums(int[] nums) {
        Arrays.sort(nums);
        int dup = -1;
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] == nums[i + 1]) {
                dup = nums[i];
                break;
            }
        }
        int expect = 1;
        int miss = -1;
        for (int x : nums) {
            if (x == expect) {
                expect++;
            } else if (x > expect) {
                miss = expect;
                break;
            }
            // if x < expect, this is the extra duplicate occurrence — skip it
        }
        if (miss == -1) {
            miss = nums.length;
        }
        return new int[] { dup, miss };
    }
}

HashSet — Time: O(n), Space: O(n):

import java.util.*;

class Solution {
    public int[] findErrorNums(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        int dup = -1;
        for (int x : nums) {
            if (!seen.add(x)) {
                dup = x;
            }
        }
        int miss = -1;
        for (int k = 1; k <= nums.length; k++) {
            if (!seen.contains(k)) {
                miss = k;
                break;
            }
        }
        return new int[] { dup, miss };
    }
}

Optimal

Cyclic sort — Time: O(n), Space: O(1) auxiliary.

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

---

5. The “Java vs. Others” Edge

• Returning pairs: return new int[] { duplicate, missing }; is idiomatic Java. In C++ you might return std::vector<int> or std::pair<int,int>; in Python a list or tuple.
• Array literals: new int[] { a, b } allocates a fixed two-slot array—perfect for LeetCode’s signature.
• Cyclic sort as the pattern answer: For “1..n with a duplicate and a missing,” cyclic sort is often the intended O(n)/O(1) solution and reads well in interviews.
• Brute-force sort: Easy to code under pressure; mention the worse time bound if you use it.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force (sort)	O(n log n)	O(1)	In-place sort; must handle missing at end (n).
Brute Force (HashSet)	O(n)	O(n)	Two concepts: detect dup, find missing.
Optimal (cyclic sort)	O(n)	O(1)	Swaps only; first mismatch gives [dup, missing].