Code Implementation

class Solution:
    def findErrorNums(self, nums):
        n = len(nums)
        num_set = set()
        duplicate = -1
        for num in nums:
            if num in num_set:
                duplicate = num
            else:
                num_set.add(num)
        for i in range(1, n + 1):
            if i not in num_set:
                missing = i
                break
        return [duplicate, missing]
      

class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        int n = nums.size();
        vector<bool> seen(n + 1, false);
        int duplicate = -1, missing = -1;
        for (int num : nums) {
            if (seen[num]) {
                duplicate = num;
            } else {
                seen[num] = true;
            }
        }
        for (int i = 1; i <= n; ++i) {
            if (!seen[i]) {
                missing = i;
                break;
            }
        }
        return {duplicate, missing};
    }
};
      

class Solution {
    public int[] findErrorNums(int[] nums) {
        int n = nums.length;
        boolean[] seen = new boolean[n + 1];
        int duplicate = -1, missing = -1;
        for (int num : nums) {
            if (seen[num]) {
                duplicate = num;
            } else {
                seen[num] = true;
            }
        }
        for (int i = 1; i <= n; i++) {
            if (!seen[i]) {
                missing = i;
                break;
            }
        }
        return new int[]{duplicate, missing};
    }
}
      

var findErrorNums = function(nums) {
    let n = nums.length;
    let seen = new Array(n + 1).fill(false);
    let duplicate = -1, missing = -1;
    for (let num of nums) {
        if (seen[num]) {
            duplicate = num;
        } else {
            seen[num] = true;
        }
    }
    for (let i = 1; i <= n; i++) {
        if (!seen[i]) {
            missing = i;
            break;
        }
    }
    return [duplicate, missing];
};
      

Problem Description

You are given an array nums containing n integers where the numbers are supposed to be the integers from 1 to n (inclusive), but:

• One number in nums appears twice (the duplicate).
• One number from 1 to n is missing from nums.

Your task is to find both the duplicate number and the missing number, and return them as a list or array: [duplicate, missing].

Constraints:

• There is exactly one duplicate and one missing number.
• Each number in nums is in the range [1, n].
• Do not reuse the same element for both answers.

Thought Process

The first idea that comes to mind is to count how many times each number from 1 to n appears in nums. If a number appears twice, it's the duplicate. If a number never appears, it's the missing one.

A brute-force way would be to check, for each number in 1 to n, how many times it appears in nums (using a loop inside a loop). But this would be slow for large arrays, as it would take O(n²) time.

To optimize, we can use a data structure that helps us count occurrences efficiently, like a hash map or an array. This way, we can find the duplicate and missing numbers in just two passes over the data.

The key insight is: by tracking which numbers we've seen, we can instantly spot the duplicate, and by checking which number is never seen, we find the missing one.

Solution Approach

• Step 1: Create a data structure to track which numbers have been seen. This can be a set, a hash map, or a boolean array of size n+1 (since numbers go from 1 to n).
• Step 2: Iterate through nums. For each number:
  • If it's already marked as seen, that's the duplicate.
  • Otherwise, mark it as seen.
• Step 3: After processing all numbers, loop from 1 to n. The number that was never seen is the missing number.
• Step 4: Return both the duplicate and missing numbers as an array or list.

We use a set or boolean array because checking if a number has been seen is O(1) time, making the overall solution efficient. This approach is easy to understand and avoids unnecessary nested loops.

Example Walkthrough

Let's walk through the example nums = [1, 2, 2, 4]:

1. Initialize a set or boolean array to keep track of seen numbers.
2. Iterate through nums:
   • See 1: not seen before, mark as seen.
   • See 2: not seen before, mark as seen.
   • See 2: already seen! This is the duplicate.
   • See 4: not seen before, mark as seen.
3. Now, check numbers from 1 to 4:
   • 1: seen
   • 2: seen
   • 3: not seen — this is the missing number.
   • 4: seen
4. Return [2, 3] — 2 is the duplicate, 3 is missing.

Time and Space Complexity

• Brute-force approach:
  • For each number from 1 to n, count how many times it appears in nums (using a nested loop).
  • Time complexity: O(n²) — not efficient for large inputs.
  • Space complexity: O(1) (no extra data structures needed).
• Optimized approach (using set or boolean array):
  • Time complexity: O(n) — one pass to find the duplicate, one pass to find the missing number.
  • Space complexity: O(n) — for the set or boolean array.

The optimized solution is much faster, especially as n grows.

Summary

The Set Mismatch problem is solved efficiently by tracking which numbers have been seen using a set or boolean array. This lets us quickly identify the duplicate and missing numbers in a single scan, avoiding slow nested loops. The solution is elegant because it leverages simple data structures and clear logic, making it both fast and easy to understand.