# LeetCode 442: Find All Duplicates in an Array

## Problem Restatement

We are given an integer array `nums`.

The array has length `n`.

Every number satisfies:

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

Each integer appears either:

| Frequency | Meaning |
|---|---|
| Once | Normal value |
| Twice | Duplicate value |

We need to return all numbers that appear exactly twice.

The solution must use:

| Requirement | Constraint |
|---|---|
| Time | `O(n)` |
| Extra space | `O(1)` excluding the answer list |

The official problem guarantees every integer appears once or twice, and values are within `[1, n]`. ([leetcode.com](https://leetcode.com/problems/find-all-duplicates-in-an-array/))

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer array `nums` |
| Output | List of duplicated integers |
| Value range | `1` to `n` |
| Frequency | Each number appears once or twice |
| Extra space | Must be constant |

Example function shape:

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

## Examples

Example 1:

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

The duplicated numbers are:

```text
2
3
```

Answer:

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

Example 2:

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

The number `1` appears twice.

Answer:

```python
[1]
```

Example 3:

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

No duplicates exist.

Answer:

```python
[]
```

## First Thought: Use a Hash Set

A simple solution is:

1. Use a set called `seen`.
2. Traverse the array.
3. If the number already exists in `seen`, add it to the answer.
4. Otherwise insert it into `seen`.

Example:

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

This works in linear time.

However, it uses extra memory proportional to `n`.

The problem explicitly asks for constant extra space.

## Key Insight

The array values lie between:

```python
1 and n
```

This is extremely important.

Because every value can map directly to an array index.

For a number `x`, its corresponding index is:

```python
x - 1
```

We can use the sign of `nums[x - 1]` as a visited marker.

For example:

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

When we see `4`:

```python
index = 4 - 1 = 3
```

We negate:

```python
nums[3]
```

to mark that `4` has been seen.

Later, when we encounter another `2`:

```python
index = 2 - 1 = 1
```

If:

```python
nums[1]
```

is already negative, then `2` has already appeared before, so `2` is a duplicate.

This lets us store visitation information directly inside the input array.

## Algorithm

Initialize an empty answer list.

Traverse every number in `nums`.

For each value:

1. Compute:

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

We use `abs` because some values may already be negative.

2. If:

```python
nums[index] < 0
```

then we have already visited this number before, so it is duplicated.

Append:

```python
index + 1
```

to the answer.

3. Otherwise, negate:

```python
nums[index]
```

to mark the number as seen.

Return the answer list.

## Correctness

Each number `x` maps uniquely to index:

```python
x - 1
```

Initially, all array values are positive.

When the algorithm sees `x` for the first time, it negates the value at index `x - 1`. Therefore, after the first occurrence of `x`, the value at that index becomes negative.

When the algorithm later sees `x` again, the value at index `x - 1` is already negative. This means `x` has appeared before, so `x` is duplicated and is added to the answer.

Because every number appears at most twice, each duplicate is added exactly once.

No non-duplicate number is added, because its mapped index becomes negative only after its first occurrence, and no second occurrence exists.

Therefore, the algorithm returns exactly all duplicated numbers.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | Each element is processed once |
| Space | `O(1)` | Only the output list is extra storage |

The input array itself is reused as marking storage.

## Implementation

```python
class Solution:
    def findDuplicates(self, nums: list[int]) -> list[int]:
        duplicates = []

        for num in nums:
            index = abs(num) - 1

            if nums[index] < 0:
                duplicates.append(index + 1)
            else:
                nums[index] = -nums[index]

        return duplicates
```

## Code Explanation

We store duplicates here:

```python
duplicates = []
```

For each number:

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

we compute its mapped index:

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

The `abs` is necessary because the array values may already have been negated earlier.

If the mapped position is already negative:

```python
if nums[index] < 0:
```

then this number has appeared before.

So we add the original number:

```python
duplicates.append(index + 1)
```

Otherwise, we mark it as visited:

```python
nums[index] = -nums[index]
```

Finally, we return all detected duplicates.

## Testing

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

    assert sorted(
        s.findDuplicates([4,3,2,7,8,2,3,1])
    ) == [2, 3]

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

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

    assert sorted(
        s.findDuplicates([2,2,3,3])
    ) == [2, 3]

    assert s.findDuplicates([5,4,6,7,9,3,10,9,5,6]) == [9, 5, 6]

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Standard example | Checks multiple duplicates |
| Single duplicate | Checks smallest duplicate case |
| No duplicates | Checks empty answer |
| Multiple repeated pairs | Checks several duplicates |
| Larger mixed input | Checks many index markings |