#645

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Set Mismatch

Identify the duplicated and missing numbers in an integer array using array scanning combined with hash table lookup efficiently.

array hash table bit manipulation sorting

Problem Statement

You are given an integer array nums representing a set originally containing all integers from 1 to n. Due to a data error, one number in the array occurs twice while another number is missing.

Your task is to return an array containing two elements: the first is the number that occurs twice, and the second is the missing number. Ensure your solution efficiently scans the array and identifies the anomaly without sorting the entire data unless necessary.

Examples

Example 1

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

Output: [2,3]

Example details omitted.

Example 2

Input: nums = [1,1]

Output: [1,2]

Example details omitted.

Constraints

2 <= nums.length <= 104
1 <= nums[i] <= 104

Solution Approach

Hash Set Tracking

Iterate through nums while adding elements to a hash set. When an element already exists in the set, mark it as the duplicate. Then iterate from 1 to n to find the number not present in the set, which is the missing number. This directly applies array scanning plus hash lookup.

Sum Difference Method

Compute the expected sum of numbers from 1 to n and subtract the actual sum of nums to get the difference between missing and duplicate numbers. Use the hash set or scanning approach to pinpoint the duplicate, then deduce the missing number. This avoids extra iterations over the array.

Bit Manipulation Alternative

Use XOR across all numbers in nums and from 1 to n to obtain the XOR of the missing and duplicate numbers. Separate numbers by one differing bit and XOR again to isolate the duplicate and missing. This is a low-space solution leveraging array scanning patterns with bit-level checks.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) because each element is scanned once or a constant number of times. Space complexity is O(n) if using a hash set, but can be reduced to O(1) with the bit manipulation or sum difference methods.

What Interviewers Usually Probe

Expect an initial check for duplicates during array traversal.
Look for use of hash set or in-place marking to detect repeated numbers.
Confirm candidate recognizes missing number derivation using sum or XOR differences.

Common Pitfalls or Variants

Common pitfalls

Overlooking that the array may not be sorted and assuming sequential indices.
Double-counting elements or miscalculating the missing number after finding the duplicate.
Using inefficient nested loops instead of O(n) scanning and hash tracking.

Follow-up variants

The array could contain multiple duplicates with multiple missing numbers, requiring generalized mapping.
Input array might be read-only, pushing the solution toward XOR or arithmetic methods.
Numbers could span a larger range with gaps, emphasizing the need for scalable hash-based scanning.

FAQ

What is the fastest way to solve Set Mismatch using array scanning?

Scan the array once while recording elements in a hash set to detect the duplicate, then identify the missing number by comparing against the expected sequence.

Can this problem be solved without extra space?

Yes, using arithmetic sums or XOR operations allows O(1) extra space while still identifying the duplicate and missing numbers.

Why is hash table lookup useful in Set Mismatch?

It allows immediate detection of repeated elements during scanning, preventing multiple passes or sorting, which aligns with the array scanning plus hash lookup pattern.

What are common mistakes when implementing this solution?

Ignoring array bounds, miscalculating sums, or assuming the array is sorted can lead to incorrect identification of duplicates and missing numbers.

Does GhostInterview provide a step-by-step solution for Set Mismatch?

Yes, it guides through scanning, hash tracking, and optional bit manipulation, helping you execute the solution efficiently during practice.

terminal

Solution

Solution 1: Mathematics

We denote $s_1$ as the sum of all numbers from $[1,..n]$, $s_2$ as the sum of the numbers in the array $nums$ after removing duplicates, and $s$ as the sum of the numbers in the array $nums$.

1

2

3

4

5

6

7

class Solution:
    def findErrorNums(self, nums: List[int]) -> List[int]:
        n = len(nums)
        s1 = (1 + n) * n // 2
        s2 = sum(set(nums))
        s = sum(nums)
        return [s - s2, s1 - s2]

Solution 2: Hash Table

We can also use a more intuitive method, using a hash table $cnt$ to count the occurrence of each number in the array $nums$.

1

2

3

4

5

6

7

class Solution:
    def findErrorNums(self, nums: List[int]) -> List[int]:
        n = len(nums)
        s1 = (1 + n) * n // 2
        s2 = sum(set(nums))
        s = sum(nums)
        return [s - s2, s1 - s2]

Solution 3: Bit Operation

According to the properties of the XOR operation, for integer $x$, we have $x \oplus x = 0$ and $x \oplus 0 = x$. Therefore, if we perform the XOR operation on all elements in the array $nums$ and all numbers $i \in [1, n]$, we can eliminate the numbers that appear twice, leaving only the XOR result of the missing number and the duplicate number, i.e., $xs = a \oplus b$.

1

2

3

4

5

6

7

class Solution:
    def findErrorNums(self, nums: List[int]) -> List[int]:
        n = len(nums)
        s1 = (1 + n) * n // 2
        s2 = sum(set(nums))
        s = sum(nums)
        return [s - s2, s1 - s2]

Continue Practicing

#268 missing number #632 smallest range covering elements from k lists #621 task scheduler