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:

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

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.

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

Alternative Solution: Sum and Set

We can also solve this with sums.

Let:

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.

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: