# LeetCode 961: N-Repeated Element in Size 2N Array

## Problem Restatement

We are given an integer array `nums`.

The array has these properties:

| Property | Meaning |
|---|---|
| `nums.length == 2 * n` | The array has even length |
| `nums` contains `n + 1` unique values | There are fewer unique values than total values |
| One value appears exactly `n` times | This is the value we must return |
| All other values appear once | No other value is duplicated |

Return the value that appears `n` times.

The official constraints include `2 <= n <= 5000`, `nums.length == 2 * n`, and `0 <= nums[i] <= 10^4`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer array `nums` |
| Output | The element repeated `n` times |
| Guarantee | Exactly one element is repeated `n` times |

Example function shape:

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

## Examples

Example 1:

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

Output:

```python
3
```

Here `n = 2`, because the array length is `4`.

The value `3` appears `2` times.

Example 2:

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

Output:

```python
2
```

Here `n = 3`, because the array length is `6`.

The value `2` appears `3` times.

Example 3:

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

Output:

```python
5
```

Here `n = 4`, because the array length is `8`.

The value `5` appears `4` times.

## First Thought: Count Every Number

A direct solution is to count how many times each value appears.

Then return the value whose count is greater than `1`.

Example:

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

The counts are:

```python
2 -> 3
1 -> 1
5 -> 1
3 -> 1
```

So the answer is `2`.

This works, but we do not need full counts. The problem guarantee gives us a simpler approach.

## Key Insight

Only one value appears more than once.

All other values appear exactly once.

So the first duplicate we see must be the answer.

We can scan the array and store values we have already seen.

When we see a value that is already in the set, return it immediately.

## Algorithm

Create an empty set called `seen`.

For each number `x` in `nums`:

1. If `x` is already in `seen`, return `x`.
2. Otherwise, add `x` to `seen`.

Because the repeated value appears `n` times, we are guaranteed to find it.

## Correctness

The array contains exactly one value that appears `n` times. Every other value appears exactly once.

The algorithm scans the array from left to right and stores every value it has already seen.

If the algorithm finds a value already in `seen`, then that value has appeared before. Therefore, it appears at least twice.

Since all non-answer values appear exactly once, this repeated value cannot be any non-answer value. It must be the element repeated `n` times.

Because the repeated element appears multiple times, the scan will eventually encounter it after its first occurrence. At that moment, the algorithm returns it.

Therefore, the algorithm always returns exactly the required element.

## Complexity

Let `m = len(nums)`.

| Metric | Value | Why |
|---|---|---|
| Time | `O(m)` | We scan the array once |
| Space | `O(m)` | The set may store many distinct values |

Since `m = 2n`, this is also `O(n)` time and `O(n)` space.

## Implementation

```python
class Solution:
    def repeatedNTimes(self, nums: list[int]) -> int:
        seen = set()

        for x in nums:
            if x in seen:
                return x

            seen.add(x)

        return -1
```

## Code Explanation

We create a set:

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

This lets us check quickly whether a number appeared earlier.

For each number:

```python
for x in nums:
```

we check whether it has already appeared:

```python
if x in seen:
    return x
```

If yes, this value must be the repeated element.

Otherwise, we record it:

```python
seen.add(x)
```

The final return is only a safety fallback:

```python
return -1
```

For valid LeetCode input, it will not be reached.

## Testing

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

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

    assert s.repeatedNTimes([9, 9]) == 9
    assert s.repeatedNTimes([4, 1, 4, 2, 4, 3]) == 4
    assert s.repeatedNTimes([0, 1, 2, 0]) == 0

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[1,2,3,3]` | Small official-style case |
| `[2,1,2,5,3,2]` | Repeated value appears three times |
| `[5,1,5,2,5,3,5,4]` | Repeated value appears four times |
| `[9,9]` | Minimum size |
| `[4,1,4,2,4,3]` | Duplicate appears early |
| `[0,1,2,0]` | Checks value `0` |