# LeetCode 448: Find All Numbers Disappeared in an Array

## Problem Restatement

We are given an array `nums` of length `n`.

Every value in the array is in the range:

```python
1 <= nums[i] <= n
```

We need to return all numbers from `1` to `n` that do not appear in `nums`.

The official problem asks for all integers in `[1, n]` that are missing from the array. The constraints are `n == nums.length`, `1 <= n <= 10^5`, and `1 <= nums[i] <= n`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer array `nums` |
| Output | List of missing numbers |
| Value range | `1` to `n` |
| Array length | `n` |
| Goal | Find values in `[1, n]` absent from `nums` |

Example function shape:

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

## Examples

Example 1:

```python
nums = [4, 3, 2, 7, 8, 2, 3, 1]
```

The range is:

```python
[1, 2, 3, 4, 5, 6, 7, 8]
```

The numbers present in `nums` are:

```python
1, 2, 3, 4, 7, 8
```

The missing numbers are:

```python
[5, 6]
```

Example 2:

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

The range is:

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

Only `1` appears.

So the answer is:

```python
[2]
```

## First Thought: Use a Set

The simplest solution is to store all numbers in a set:

```python
seen = set(nums)
```

Then scan from `1` to `n` and collect values that do not appear in `seen`.

This is correct and easy.

But it uses `O(n)` extra space.

We can solve it with constant extra space by using the input array itself as a marker.

## Key Insight

Because every number is between `1` and `n`, every number can point to an index.

For a value `x`, its index is:

```python
x - 1
```

So when we see value `x`, we mark index `x - 1` as visited.

A common in-place mark is to make the value at that index negative.

For example:

```python
nums = [4, 3, 2, 7, 8, 2, 3, 1]
```

When we see `4`, we mark index `3`.

When we see `3`, we mark index `2`.

When we see `2`, we mark index `1`.

After marking all seen values, any index that still has a positive value corresponds to a missing number.

If index `i` is still positive, then number:

```python
i + 1
```

never appeared.

## Algorithm

First pass:

For each number `num` in `nums`:

1. Compute:

```python
index = abs(num) - 1
```

2. Mark the corresponding index as seen:

```python
nums[index] = -abs(nums[index])
```

We use `abs(num)` because `num` may already have been made negative by an earlier mark.

Second pass:

For every index `i`:

If:

```python
nums[i] > 0
```

then `i + 1` is missing.

Append it to the answer.

Return the answer.

## Correctness

Each value `x` in the array maps to exactly one index, `x - 1`.

During the first pass, whenever the algorithm sees `x`, it marks `nums[x - 1]` as negative. Therefore, after the first pass, `nums[x - 1]` is negative for every value `x` that appeared in the input.

Now consider a number `y` from `1` to `n`.

If `y` appeared in `nums`, then the first pass marked index `y - 1`, so `nums[y - 1]` is negative.

If `y` did not appear in `nums`, then no step ever marked index `y - 1`, so `nums[y - 1]` remains positive.

The second pass returns exactly those indices whose values remain positive, converted back to numbers by adding `1`.

Therefore, the returned list contains exactly all missing numbers.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | Two linear passes over the array |
| Space | `O(1)` | The input array is reused for marking |

The output list is not counted as extra working space.

## Implementation

```python
class Solution:
    def findDisappearedNumbers(self, nums: list[int]) -> list[int]:
        for num in nums:
            index = abs(num) - 1
            nums[index] = -abs(nums[index])

        missing = []

        for i, value in enumerate(nums):
            if value > 0:
                missing.append(i + 1)

        return missing
```

## Code Explanation

The first loop marks every value that appears:

```python
for num in nums:
```

The mapped index is:

```python
index = abs(num) - 1
```

The `abs` call is necessary because previous iterations may already have made some numbers negative.

We mark the value as seen:

```python
nums[index] = -abs(nums[index])
```

Using `-abs(...)` keeps the number negative even if it was already marked.

Then we scan the array again:

```python
for i, value in enumerate(nums):
```

Any positive value means its index was never marked:

```python
if value > 0:
    missing.append(i + 1)
```

The missing number is `i + 1`, because value `1` maps to index `0`, value `2` maps to index `1`, and so on.

## Testing

```python
def run_tests():
    s = Solution()

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

    assert s.findDisappearedNumbers(
        [1, 1]
    ) == [2]

    assert s.findDisappearedNumbers(
        [1]
    ) == []

    assert s.findDisappearedNumbers(
        [2, 2]
    ) == [1]

    assert s.findDisappearedNumbers(
        [1, 2, 3, 4, 5]
    ) == []

    assert s.findDisappearedNumbers(
        [5, 4, 3, 2, 1]
    ) == []

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Standard example | Checks multiple missing numbers |
| `[1, 1]` | Checks duplicate causing one missing number |
| Single element | Checks smallest array |
| `[2, 2]` | Checks missing first value |
| Already complete range | Checks no missing values |
| Reversed complete range | Checks order does not matter |