# 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:

```python
[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:

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

## Examples

Example 1:

```python
nums = [1, 2, 2, 4]
```

The correct set should be:

```python
[1, 2, 3, 4]
```

But `2` appears twice, and `3` is missing.

Output:

```python
[2, 3]
```

Example 2:

```python
nums = [1, 1]
```

The correct set should be:

```python
[1, 2]
```

But `1` appears twice, and `2` is missing.

Output:

```python
[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

```python
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:

```python
count = [0] * (n + 1)
```

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

Then we count the values:

```python
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`:

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

The missing number is the number with count `0`:

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

Finally, we return them in the required order:

```python
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:

```python
duplicate = actual_sum - unique_sum
missing = expected_sum - unique_sum
```

Implementation:

```python
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

```python
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 |