LeetCode 645: Set Mismatch

Problem Restatement

We are given an array nums of length n.

Originally, the array should contain every number from 1 to n exactly once.

But an error happened:

Error	Meaning
One number appears twice	This is the duplicate number
One number is missing	This is the missing number

We need to return:

[duplicate, missing]

in that exact order. The official examples include nums = [1, 2, 2, 4], which returns [2, 3], and nums = [1, 1], which returns [1, 2].

Input and Output

Item	Meaning
Input	An integer array nums
Output	A list [duplicate, missing]
Original set	Numbers from 1 to n
Error	One number duplicated, one number missing

Example function shape:

def findErrorNums(nums: list[int]) -> list[int]:
    ...

Examples

Example 1:

nums = [1, 2, 2, 4]

The correct set should be:

[1, 2, 3, 4]

But 2 appears twice, and 3 is missing.

Output:

[2, 3]

Example 2:

nums = [1, 1]

The correct set should be:

[1, 2]

But 1 appears twice, and 2 is missing.

Output:

[1, 2]

First Thought: Count Every Number

The most direct solution is to count how many times each number appears.

Then scan from 1 to n.

Count	Meaning
0	This number is missing
2	This number is duplicated
1	This number is normal

This is simple and reliable.

Algorithm

1. Create a count array of size n + 1.
2. Count every number in nums.
3. Scan numbers from 1 to n.
4. If a number has count 2, store it as duplicate.
5. If a number has count 0, store it as missing.
6. Return [duplicate, missing].

Implementation

class Solution:
    def findErrorNums(self, nums: list[int]) -> list[int]:
        n = len(nums)
        count = [0] * (n + 1)

        for num in nums:
            count[num] += 1

        duplicate = -1
        missing = -1

        for num in range(1, n + 1):
            if count[num] == 2:
                duplicate = num
            elif count[num] == 0:
                missing = num

        return [duplicate, missing]

Code Explanation

We create a count array:

count = [0] * (n + 1)

Index 0 is unused because the valid numbers are from 1 to n.

Then we count the values:

for num in nums:
    count[num] += 1

After that, each number has one of three useful counts.

The duplicate is the number with count 2:

if count[num] == 2:
    duplicate = num

The missing number is the number with count 0:

elif count[num] == 0:
    missing = num

Finally, we return them in the required order:

return [duplicate, missing]

Correctness

The array should contain every number from 1 to n exactly once.

The error duplicates one number and removes one number.

After counting all values in nums, the duplicated number is counted twice because it appears twice in the array. The missing number is counted zero times because it does not appear at all.

Every other number appears exactly once.

The algorithm scans all numbers from 1 to n, identifies the one with count 2 as duplicate, and identifies the one with count 0 as missing.

Therefore, the returned array [duplicate, missing] is correct.

Complexity

Metric	Value	Why
Time	O(n)	We count the array once and scan 1..n once
Space	O(n)	The count array stores one count per possible value

Alternative Solution: Sum and Set

We can also solve this with sums.

Let:

Value	Meaning
expected_sum	Sum of 1..n
actual_sum	Sum of all values in nums
unique_sum	Sum of distinct values in nums

Then:

duplicate = actual_sum - unique_sum
missing = expected_sum - unique_sum

Implementation:

class Solution:
    def findErrorNums(self, nums: list[int]) -> list[int]:
        n = len(nums)

        expected_sum = n * (n + 1) // 2
        actual_sum = sum(nums)
        unique_sum = sum(set(nums))

        duplicate = actual_sum - unique_sum
        missing = expected_sum - unique_sum

        return [duplicate, missing]

This works because actual_sum counts the duplicate twice, while unique_sum counts it once. Also, expected_sum includes the missing number, while unique_sum does not.

Metric	Value	Why
Time	O(n)	Sums and set construction scan the array
Space	O(n)	The set stores distinct values

Testing

def run_tests():
    s = Solution()

    assert s.findErrorNums([1, 2, 2, 4]) == [2, 3]
    assert s.findErrorNums([1, 1]) == [1, 2]
    assert s.findErrorNums([2, 2]) == [2, 1]
    assert s.findErrorNums([3, 2, 3, 4, 6, 5]) == [3, 1]
    assert s.findErrorNums([1, 5, 3, 2, 2, 7, 6, 4, 8, 9]) == [2, 10]

    print("all tests passed")

run_tests()

Test meaning:

Test	Why
[1, 2, 2, 4]	Standard example
[1, 1]	Missing number is at the end
[2, 2]	Missing number is at the beginning
[3, 2, 3, 4, 6, 5]	Unsorted input
Larger array	Confirms general counting behavior