86. Set Mismatch

🔗 LeetCode Problem: 645. Set Mismatch
📊 Difficulty: Easy
🏷️ Topics: Array, Hash Table, Bit Manipulation, Sorting

Problem Statement

You have a set of integers s, which originally contains all the numbers from 1 to n. Unfortunately, due to some error, one of the numbers in s got duplicated to another number in the set, which results in repetition of one number and loss of another number.

You are given an integer array nums representing the data status of this set after the error.

Find the number that occurs twice and the number that is missing and return them in the form of an array [duplicate, missing].

Example 1:

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

Explanation:
2 appears twice
3 is missing

Example 2:

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

Explanation:
1 appears twice
2 is missing

Constraints: - 2 <= nums.length <= 10^4 - 1 <= nums[i] <= 10^4

🌟 ELI5: The Perfect Combination Problem!

Think of a deck of numbered cards:

You should have: 1, 2, 3, 4, 5
Perfect set!

But you accidentally printed card 2 twice:
Now you have: 1, 2, 2, 4, 5

What happened?
  - Card 2 appears TWICE (duplicate)
  - Card 3 is MISSING

Return: [2, 3] ✓

The Key Insight:

This combines TWO problems:
  1. Find the duplicate number
  2. Find the missing number

Exactly ONE number appears twice
Exactly ONE number is missing

We need to find BOTH!

🎨 Visual Understanding

The Problem Visualized

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

Expected: 1, 2, 3, 4
Actual:   1, 2, 2, 4

Comparison:
  Number 1: ✓ (present)
  Number 2: ✗ (appears TWICE)
  Number 3: ✗ (MISSING)
  Number 4: ✓ (present)

Answer: [2, 3] ✓
  - 2 is the duplicate
  - 3 is the missing

Example 2: nums = [1, 1]

Expected: 1, 2
Actual:   1, 1

Comparison:
  Number 1: ✗ (appears TWICE)
  Number 2: ✗ (MISSING)

Answer: [1, 2] ✓

The Cyclic Sort Visualization

Goal: Place each number at its correct index
  Number i → Index i-1

Example: [1, 2, 2, 4]

After cyclic sort:
  Index: 0  1  2  3
  Value: 1  2  2  4

Check each position:
  Index 0: nums[0] = 1, expected 1 ✓
  Index 1: nums[1] = 2, expected 2 ✓
  Index 2: nums[2] = 2, expected 3 ✗
    → Position 2 has 2 (should be 3)
    → 2 is the duplicate!
    → 3 is the missing!

Answer: [2, 3] ✓

🎯 Approach 1: HashSet (Simple)

The Most Natural Thinking 💭

Core Logic:

Use a set to find duplicate
Then check which number 1 to n is missing

Implementation

/**
 * Using HashSet
 * Time: O(n), Space: O(n)
 */
public int[] findErrorNums(int[] nums) {
    Set<Integer> seen = new HashSet<>();
    int duplicate = -1;

    // Find duplicate
    for (int num : nums) {
        if (seen.contains(num)) {
            duplicate = num;
        }
        seen.add(num);
    }

    // Find missing
    int missing = -1;
    for (int i = 1; i <= nums.length; i++) {
        if (!seen.contains(i)) {
            missing = i;
            break;
        }
    }

    return new int[]{duplicate, missing};
}

⏰ Time: O(n) - Two passes
💾 Space: O(n) - HashSet

❌ Problem: Uses O(n) space!

🎯 Approach 2: Cyclic Sort (O(1) Space) ⭐

Better Approach 💡

🧠 The Core Insight

Use Cyclic Sort to place numbers at correct positions!

After sorting:
  The position with wrong number reveals BOTH:
    - The number at that position = duplicate
    - The expected number = missing

Perfect for this problem!

Implementation

/**
 * Cyclic Sort - Find Both Duplicate and Missing
 * Time: O(n), Space: O(1)
 */
public int[] findErrorNums(int[] nums) {
    int i = 0;

    // STEP 1: Cyclic sort
    while (i < nums.length) {
        int correctIndex = nums[i] - 1;

        // If number is not at correct position
        if (nums[i] != nums[correctIndex]) {
            swap(nums, i, correctIndex);
        } else {
            i++;
        }
    }

    // STEP 2: Find duplicate and missing
    for (i = 0; i < nums.length; i++) {
        if (nums[i] != i + 1) {
            // nums[i] is the duplicate (wrong number at this position)
            // i + 1 is the missing (expected number)
            return new int[]{nums[i], i + 1};
        }
    }

    return new int[]{-1, -1};  // Should never reach
}

private void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

⏰ Time: O(n) - Each number swaps at most once
💾 Space: O(1) - In-place

🔍 Super Detailed Dry Run

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

Goal: Find [duplicate, missing] = [2, 3]

═══════════════════════════════════════════════════════════════
STEP 1: Cyclic Sort
═══════════════════════════════════════════════════════════════

Initial: [1, 2, 2, 4]
         Index: 0  1  2  3

i = 0:
  nums[0] = 1
  correctIndex = 1 - 1 = 0

  nums[0] != nums[0]? 1 != 1? No!
  Already at correct position! i++

  Array: [1, 2, 2, 4]
         i = 1

i = 1:
  nums[1] = 2
  correctIndex = 2 - 1 = 1

  nums[1] != nums[1]? 2 != 2? No!
  Already at correct position! i++

  Array: [1, 2, 2, 4]
         i = 2

i = 2:
  nums[2] = 2
  correctIndex = 2 - 1 = 1

  nums[2] != nums[1]? 2 != 2? No!
  They're equal! (duplicate!)
  Can't swap, i++

  Array: [1, 2, 2, 4]
         i = 3

i = 3:
  nums[3] = 4
  correctIndex = 4 - 1 = 3

  Already at correct position! i++

  Array: [1, 2, 2, 4]
         i = 4

i = 4, exit while loop

Final sorted: [1, 2, 2, 4]

═══════════════════════════════════════════════════════════════
STEP 2: Find Duplicate and Missing
═══════════════════════════════════════════════════════════════

Check each index:

i = 0:
  nums[0] = 1
  Expected: i + 1 = 0 + 1 = 1
  1 == 1? Yes ✓
  Continue

i = 1:
  nums[1] = 2
  Expected: i + 1 = 1 + 1 = 2
  2 == 2? Yes ✓
  Continue

i = 2:
  nums[2] = 2
  Expected: i + 1 = 2 + 1 = 3
  2 == 3? No ✗

  Found mismatch!
  nums[2] = 2 → This is the duplicate!
  i + 1 = 3 → This is the missing!

  Return [2, 3] ✓

Result: [2, 3]

Example 2: nums = [1, 1]

Initial: [1, 1]

═══════════════════════════════════════════════════════════════
Cyclic Sort
═══════════════════════════════════════════════════════════════

i = 0:
  nums[0] = 1
  correctIndex = 1 - 1 = 0

  Already at correct position! i++

  Array: [1, 1]
         i = 1

i = 1:
  nums[1] = 1
  correctIndex = 1 - 1 = 0

  nums[1] != nums[0]? 1 != 1? No!
  Equal (duplicate)! i++

  Array: [1, 1]
         i = 2

i = 2, exit while loop

Final: [1, 1]

═══════════════════════════════════════════════════════════════
Find Mismatch
═══════════════════════════════════════════════════════════════

i = 0:
  nums[0] = 1, expected 1 ✓

i = 1:
  nums[1] = 1, expected 2 ✗

  Duplicate: 1
  Missing: 2

  Return [1, 2] ✓

Result: [1, 2]

Example 3: nums = [3, 2, 3, 4, 6, 5]

Initial: [3, 2, 3, 4, 6, 5]

═══════════════════════════════════════════════════════════════
Cyclic Sort
═══════════════════════════════════════════════════════════════

i = 0: nums[0] = 3, correctIndex = 2
  Swap with index 2
  [3, 2, 3, 4, 6, 5]
  i stays at 0

i = 0: nums[0] = 3, correctIndex = 2
  nums[0] != nums[2]? 3 != 3? No!
  Duplicate! i++

i = 1: nums[1] = 2, correctIndex = 1
  Already correct! i++

i = 2: nums[2] = 3, correctIndex = 2
  Already correct! i++

i = 3: nums[3] = 4, correctIndex = 3
  Already correct! i++

i = 4: nums[4] = 6, correctIndex = 5
  Swap with index 5
  [3, 2, 3, 4, 5, 6]
  i stays at 4

i = 4: nums[4] = 5, correctIndex = 4
  Already correct! i++

i = 5: nums[5] = 6, correctIndex = 5
  Already correct! i++

Final: [3, 2, 3, 4, 5, 6]

═══════════════════════════════════════════════════════════════
Find Mismatch
═══════════════════════════════════════════════════════════════

i = 0: nums[0] = 3, expected 1 ✗
  Duplicate: 3
  Missing: 1

  Return [3, 1] ✓

Result: [3, 1]

🎯 Approach 3: Math (Sum Formula)

Another O(1) Space Approach 💡

🧠 The Mathematical Insight

Use two equations:

1. Sum of all numbers
   Expected sum: 1+2+...+n = n(n+1)/2
   Actual sum: sum of nums array
   Difference = missing - duplicate

2. Sum of squares
   Expected: 1²+2²+...+n² = n(n+1)(2n+1)/6
   Actual: sum of (nums[i])²
   Difference = missing² - duplicate²

Solve these two equations!

Implementation

/**
 * Using Math - Sum and Sum of Squares
 * Time: O(n), Space: O(1)
 */
public int[] findErrorNums(int[] nums) {
    int n = nums.length;

    // Expected sum: 1+2+...+n
    long expectedSum = (long) n * (n + 1) / 2;
    long actualSum = 0;

    // Expected sum of squares: 1²+2²+...+n²
    long expectedSumSq = (long) n * (n + 1) * (2 * n + 1) / 6;
    long actualSumSq = 0;

    for (int num : nums) {
        actualSum += num;
        actualSumSq += (long) num * num;
    }

    // missing - duplicate = expectedSum - actualSum
    long diff = expectedSum - actualSum;

    // missing² - duplicate² = expectedSumSq - actualSumSq
    // (missing - duplicate)(missing + duplicate) = expectedSumSq - actualSumSq
    long sumDiffSq = expectedSumSq - actualSumSq;

    // missing + duplicate = sumDiffSq / diff
    long sum = sumDiffSq / diff;

    // Solve:
    // missing - duplicate = diff
    // missing + duplicate = sum
    // => 2*missing = diff + sum
    int missing = (int) ((diff + sum) / 2);
    int duplicate = (int) (missing - diff);

    return new int[]{duplicate, missing};
}

⏰ Time: O(n) - Single pass
💾 Space: O(1) - Only variables

✓ No sorting needed!

🎯 Comparison of All Approaches

Approach          Time    Space   Modifies   Notes
═══════════════════════════════════════════════════════════════
HashSet           O(n)    O(n)    No         Simple
Cyclic Sort       O(n)    O(1)    Yes        Most intuitive
Math Formula      O(n)    O(1)    No         Clever!

Recommended for Interview: Cyclic Sort (clearest logic)
Most Elegant: Math Formula (no modification)

🎯 Why Cyclic Sort Works Perfectly

The Beauty of This Problem:
═══════════════════════════════════════════════════════════════

After cyclic sort, exactly ONE position will have wrong value!

Why?
  - We have n positions (0 to n-1)
  - We have n numbers (but one duplicate, one missing)

  Example: [1, 2, 2, 4]
    Position 0: Should have 1, has 1 ✓
    Position 1: Should have 2, has 2 ✓
    Position 2: Should have 3, has 2 ✗ (duplicate!)
    Position 3: Should have 4, has 4 ✓

The Wrong Position Tells Us Everything:
═══════════════════════════════════════════════════════════════

At position i where nums[i] != i+1:
  - nums[i] = the duplicate (wrong number here)
  - i+1 = the missing (expected number)

This is EXACTLY what we need! ✓

Time Complexity:
═══════════════════════════════════════════════════════════════

Cyclic sort: O(n)
  Each number swaps at most once

Find mismatch: O(n)
  Single pass through array

Total: O(n) ✓

Space: O(1) ✓

🎯 Why Math Approach Works

The Mathematical Proof:
═══════════════════════════════════════════════════════════════

Let:
  d = duplicate
  m = missing

We have two unknowns, need two equations!

Equation 1: Sum difference
  Expected: 1+2+...+n
  Actual: 1+2+...+n - m + d (m missing, d added)

  expectedSum - actualSum = m - d ... (1)

Equation 2: Sum of squares difference
  Expected: 1²+2²+...+n²
  Actual: 1²+2²+...+n² - m² + d²

  expectedSumSq - actualSumSq = m² - d²
                                = (m-d)(m+d) ... (2)

From (1): m - d = diff
From (2): (m-d)(m+d) = sumDiffSq
          diff × (m+d) = sumDiffSq
          m + d = sumDiffSq / diff ... (3)

Solve (1) and (3):
  m - d = diff
  m + d = sum (where sum = sumDiffSq/diff)

  Add: 2m = diff + sum
       m = (diff + sum) / 2

  Substitute: d = m - diff

Done! ✓

Example: [1, 2, 2, 4]
  expectedSum = 10
  actualSum = 9
  diff = 1

  expectedSumSq = 30
  actualSumSq = 25
  sumDiffSq = 5

  sum = 5/1 = 5
  m = (1+5)/2 = 3
  d = 3-1 = 2

  Answer: [2, 3] ✓

⚠️ Common Mistakes to Avoid

Mistake 1: Wrong order in result

// ❌ WRONG - Missing before duplicate
return new int[]{missing, duplicate};

// ✓ CORRECT - Duplicate before missing
return new int[]{duplicate, missing};

Problem asks for [duplicate, missing]!

Mistake 2: Not handling duplicate during sort

// ❌ WRONG - Infinite loop
while (i < n) {
    int correctIdx = nums[i] - 1;
    if (nums[i] != nums[correctIdx]) {
        swap(nums, i, correctIdx);
    }
    // Missing i++!
}

// ✓ CORRECT
if (nums[i] != nums[correctIdx]) {
    swap(nums, i, correctIdx);
} else {
    i++;  // Important for duplicate!
}

Mistake 3: Math overflow

// ❌ WRONG - Integer overflow!
int expectedSum = n * (n + 1) / 2;

// ✓ CORRECT - Use long
long expectedSum = (long) n * (n + 1) / 2;

Mistake 4: Division by zero check

// ❌ WRONG - Might divide by zero
long sum = sumDiffSq / diff;

// ✓ CORRECT - Should be safe (diff never 0)
// But in production, add check:
if (diff == 0) return new int[]{-1, -1};
long sum = sumDiffSq / diff;

🎯 Pattern Recognition

Problem Type: Find Duplicate AND Missing
Core Pattern: Cyclic Sort (Perfect Match!)

When to Apply:
✓ Array with values in [1, n]
✓ One duplicate, one missing
✓ Need O(1) space
✓ Can modify array

Recognition Keywords:
- "One number duplicated"
- "One number missing"
- "Return both"
- "Values from 1 to n"

Similar Problems:
- Find Duplicate (LC 287) - Only duplicate
- Missing Number (LC 268) - Only missing
- Find All Duplicates (LC 442) - Multiple duplicates

Key Components:
┌────────────────────────────────────────────┐
│ Cyclic sort to correct positions         │
│ Find first nums[i] != i+1                │
│ That position has:                       │
│   - nums[i] = duplicate                  │
│   - i+1 = missing                        │
│ Time: O(n), Space: O(1)                  │
└────────────────────────────────────────────┘

Perfect problem for cyclic sort!

🧠 Interview Strategy

Step 1: "One duplicate, one missing - classic set mismatch"
Step 2: "Cyclic sort places numbers at correct positions"
Step 3: "Position with wrong value reveals both"
Step 4: "nums[i] is duplicate, i+1 is missing"
Step 5: "O(n) time, O(1) space"

Key Points to Mention:
- Cyclic sort: place i at index i-1
- After sorting, exactly one position wrong
- That position reveals both answers
- nums[i] = duplicate (wrong number there)
- i+1 = missing (expected number)
- Handle duplicate during sort (else clause)
- Return [duplicate, missing] (order matters!)
- Time: O(n), Space: O(1)

Why This Approach?
"This problem is perfect for cyclic sort. I place each number at
its correct index (number i at index i-1). After sorting, exactly
one position will have the wrong value - that position tells me
everything: the value there is the duplicate, and the expected
value (i+1) is the missing number. This gives O(n) time with O(1)
space by modifying the array in-place."

Alternative Mention:
"There's also a clever math approach using sum and sum-of-squares
formulas to solve two equations with two unknowns, which doesn't
modify the array. But cyclic sort is more intuitive."

Edge Cases to Mention:
✓ Duplicate at start
✓ Duplicate at end
✓ Missing is 1
✓ Missing is n
✓ Small array (n=2)

📝 Quick Revision Notes

🎯 Core Concept:

Set Mismatch: One duplicate, one missing. Cyclic sort: place i at index i-1. After sort, find first nums[i] != i+1. That position reveals: nums[i] = duplicate, i+1 = missing. Return [duplicate, missing]. O(n) time, O(1) space!

⚡ Quick Implementation:

import java.util.Arrays;

class Solution {
  public int[] findErrorNums(int[] a) {
    // Approach 1 - using cycli sort.
    // key logic: at index i, number i+1 should be present
    // checks: number being swapped at target index should not be the same. Else infinite loop.
    int[] res = new int[2];
    int i = 0;
    int len = a.length;

    while (i < len) {
      if(i + 1 != a[i] && a[i] != a[a[i] - 1]) {
        swap(a, i, a[i] - 1);
      } else {
        i++;
      }
    }

    for(i = 0; i < len; i++) {
      if(i + 1 != a[i]) {
        res[0] = a[i];
        res[1] = i + 1;
      }
    }

    return res;
  }

  private void swap(int[] a, int i, int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
  }

  public static void main(String[] args) {
    Solution t = new Solution();
    System.out.println(Arrays.toString(t.findErrorNums(new int[] {1,2,2,4})));
    System.out.println(Arrays.toString(t.findErrorNums(new int[] {1,1})));
  }
}

🔑 Key Insights:

Pattern: Cyclic Sort (perfect fit!)
After sort: Exactly ONE position wrong
That position: nums[i] = dup, i+1 = missing
Order: [duplicate, missing] (matters!)
Handle dup: In else clause (i++)
Time: O(n), Space: O(1)

🎪 Memory Aid:

"Sort to spots, find wrong spot, it reveals both!"
Think: "Position tells all: value=dup, index+1=missing!" ✨

💡 The Perfect Match:

Why cyclic sort is PERFECT here:

After sorting [1,2,2,4]:
  [1, 2, 2, 4]
   ✓  ✓  ✗  ✓

Position 2 is wrong!
  Has: 2 (the duplicate!)
  Should have: 3 (the missing!)

Both answers from ONE position! ✓

🧪 Edge Cases

Case 1: Duplicate at start

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

Case 2: Duplicate at end

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

Case 3: Missing is 1

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

Case 4: Missing is n

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

Case 5: Middle duplicate

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

All handled correctly! ✓

Missing Number (LC 268) - Only missing
Find Duplicate Number (LC 287) - Only duplicate
Find All Duplicates (LC 442) - Multiple duplicates

Happy practicing! 🎯

Note: This problem beautifully combines finding a duplicate AND a missing number. Cyclic sort is the PERFECT pattern because after sorting, exactly one position reveals both answers! This is an elegant example of how the right pattern makes a complex problem simple! 💪✨

86. Set Mismatch

Problem Statement

🌟 ELI5: The Perfect Combination Problem!

🎨 Visual Understanding

The Problem Visualized

The Cyclic Sort Visualization

🎯 Approach 1: HashSet (Simple)

The Most Natural Thinking 💭

Implementation

🎯 Approach 2: Cyclic Sort (O(1) Space) ⭐

Better Approach 💡

Implementation

🔍 Super Detailed Dry Run

🎯 Approach 3: Math (Sum Formula)

Another O(1) Space Approach 💡

Implementation

🎯 Comparison of All Approaches

🎯 Why Cyclic Sort Works Perfectly

🎯 Why Math Approach Works

⚠️ Common Mistakes to Avoid

🎯 Pattern Recognition

🧠 Interview Strategy

📝 Quick Revision Notes

🧪 Edge Cases

Related Patterns