What is the time complexity of the Hash Set approach?

The Hash Set approach has O(n) time complexity as we iterate through the array once and then check numbers 1 to n.

Which approach uses O(1) extra space?

The Mathematical, Bit Manipulation, Negation Marking, and Cyclic Sort approaches all use O(1) extra space.

What is the fastest approach for Set Mismatch?

The Hash Set, Mathematical, Bit Manipulation, Negation Marking, and Cyclic Sort approaches all have O(n) time complexity, making them equally efficient in terms of time.

Does the Sorting approach modify the input array?

Yes, the Sorting approach modifies the input array by sorting it in place.

Which approach is recommended for interview?

The Negation Marking or Cyclic Sort approaches are often recommended as they demonstrate clever use of the input array for O(1) space without complex math.

Set Mismatch | N3mo LC

Difficulty: Easy | Acceptance: 43.70% | Paid: No Topics: Array, Hash Table, Bit Manipulation, Sorting

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.

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

Examples
Constraints
Approach 1: Hash Set
Approach 2: Sorting
Approach 3: Mathematical
Approach 4: Bit Manipulation
Approach 5: Negation Marking
Approach 6: Cyclic Sort

Examples

Example 1

Input:

nums = [1,2,2,4]

Output:

[2,3]

Example 2

Input:

nums = [1,1]

Output:

[1,2]

Constraints

2 <= nums.length <= 10⁴
1 <= nums[i] <= 10⁴

Hash Set

Intuition Use a hash set to track seen numbers. The number already in the set is the duplicate, and the number from 1 to n not in the set is the missing number.

Steps

Create a hash set to store seen numbers
Iterate through the array, checking if each number is already in the set
If found, it’s the duplicate; otherwise, add it to the set
After iteration, check numbers 1 to n to find which one is missing from the set

python

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

Complexity

Time: O(n)
Space: O(n)
Notes: Simple and intuitive but uses extra space for the hash set

Sorting

Intuition Sort the array first, then iterate to find adjacent equal elements (duplicate) and the gap where expected number doesn’t match actual (missing).

Steps

Sort the array in ascending order
Iterate through the sorted array
If current element equals previous element, it’s the duplicate
If current element is not equal to its expected value (index + 1), it’s the missing number

python

class Solution:
    def findErrorNums(self, nums):
        nums.sort()
        n = len(nums)
        duplicate = -1
        missing = -1
        
        for i in range(1, n):
            if nums[i] == nums[i - 1]:
                duplicate = nums[i]
            elif nums[i] &gt; nums[i - 1] + 1:
                missing = nums[i - 1] + 1
        
        if missing == -1:
            if nums[0] != 1:
                missing = 1
            else:
                missing = n
        
        return [duplicate, missing]

Complexity

Time: O(n log n)
Space: O(1) or O(n) depending on sorting implementation
Notes: Sorting adds time complexity but can be done in-place

Mathematical

Intuition Use the sum and sum of squares formulas to create two equations with two unknowns (missing and duplicate), then solve them simultaneously.

Steps

Calculate expected sum of 1 to n: n*(n+1)/2
Calculate actual sum of array
The difference gives us (missing - duplicate)
Calculate expected sum of squares: n*(n+1)*(2n+1)/6
Calculate actual sum of squares
The difference gives us (missing² - duplicate²) = (missing - duplicate)(missing + duplicate)
Divide sum of squares difference by sum difference to get (missing + duplicate)
Solve the two equations to find missing and duplicate

python

class Solution:
    def findErrorNums(self, nums):
        n = len(nums)
        expected_sum = n * (n + 1) // 2
        actual_sum = sum(nums)
        
        expected_sum_sq = n * (n + 1) * (2 * n + 1) // 6
        actual_sum_sq = sum(x * x for x in nums)
        
        diff = expected_sum - actual_sum  # missing - duplicate
        diff_sq = expected_sum_sq - actual_sum_sq  # missing^2 - duplicate^2
        
        sum_val = diff_sq // diff  # missing + duplicate
        
        missing = (diff + sum_val) // 2
        duplicate = (sum_val - diff) // 2
        
        return [duplicate, missing]

Complexity

Time: O(n)
Space: O(1)
Notes: Elegant mathematical solution but requires careful handling of large numbers

Bit Manipulation

Intuition XOR all numbers from 1 to n with all array elements. The result is (missing XOR duplicate). Use this to separate and identify both numbers.

Steps

XOR all numbers from 1 to n with all array elements
The result is xor = missing XOR duplicate
Find any set bit in xor (rightmost set bit)
Partition all numbers (1 to n and array elements) into two groups based on this bit
XOR each group separately to get missing and duplicate
Determine which is which by checking the original array

python

class Solution:
    def findErrorNums(self, nums):
        n = len(nums)
        xor = 0
        
        for i in range(1, n + 1):
            xor ^= i
        
        for num in nums:
            xor ^= num
        
        # xor = missing ^ duplicate
        # Find rightmost set bit
        rightmost_bit = xor & (-xor)
        
        num1, num2 = 0, 0
        
        for i in range(1, n + 1):
            if i & rightmost_bit:
                num1 ^= i
            else:
                num2 ^= i
        
        for num in nums:
            if num & rightmost_bit:
                num1 ^= num
            else:
                num2 ^= num
        
        # Determine which is duplicate
        for num in nums:
            if num == num1:
                return [num1, num2]
        
        return [num2, num1]

Complexity

Time: O(n)
Space: O(1)
Notes: Constant space solution using XOR properties, but more complex to understand

Negation Marking

Intuition Use the array itself as a marker by negating values at indices. When we encounter a negative value at an index, that number is the duplicate.

Steps

Iterate through the array
For each number, use its absolute value as an index
If the value at that index is already negative, the current number is the duplicate
Otherwise, negate the value at that index
After first pass, the index with positive value indicates the missing number

python

class Solution:
    def findErrorNums(self, nums):
        n = len(nums)
        duplicate = -1
        
        for num in nums:
            idx = abs(num) - 1
            if nums[idx] &lt; 0:
                duplicate = abs(num)
            else:
                nums[idx] = -nums[idx]
        
        missing = -1
        for i in range(n):
            if nums[i] &gt; 0:
                missing = i + 1
                break
        
        return [duplicate, missing]

Complexity

Time: O(n)
Space: O(1)
Notes: Modifies the input array in-place, uses negation as a marker

Cyclic Sort

Intuition Place each number at its correct index (number-1). The number that can’t be placed is the duplicate, and the index where the number doesn’t match is the missing number.

Steps

Iterate through the array
For each position, swap the current number to its correct index (number-1)
If the correct position already has the same number, it’s the duplicate
After sorting, find the index where number doesn’t equal index+1 to get the missing number

python

class Solution:
    def findErrorNums(self, nums):
        n = len(nums)
        i = 0
        duplicate = -1
        
        while i &lt; n:
            correct_idx = nums[i] - 1
            if nums[i] != nums[correct_idx]:
                nums[i], nums[correct_idx] = nums[correct_idx], nums[i]
            else:
                if i != correct_idx:
                    duplicate = nums[i]
                i += 1
        
        missing = -1
        for i in range(n):
            if nums[i] != i + 1:
                missing = i + 1
                break
        
        return [duplicate, missing]

Complexity

Time: O(n)
Space: O(1)
Notes: Modifies the input array, optimal for range-based problems