# LeetCode 575: Distribute Candies

## Problem Restatement

We are given an integer array `candyType`.

Each integer represents one candy type.

Alice has `n` candies total, where `n = len(candyType)`. She is allowed to eat exactly `n / 2` candies.

Return the maximum number of different candy types Alice can eat.

The array length is even. The constraints include `n == candyType.length`, `1 <= n <= 10^4`, `n` is even, and `-10^5 <= candyType[i] <= 10^5`. The examples include `[1,1,2,2,3,3]`, output `3`, and `[1,1,2,3]`, output `2`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | An integer array `candyType` |
| Output | Maximum number of different candy types Alice can eat |
| Alice eats | Exactly `len(candyType) / 2` candies |
| Goal | Maximize the number of distinct types eaten |

Example function shape:

```python
def distributeCandies(candyType: list[int]) -> int:
    ...
```

## Examples

Example 1:

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

There are `6` candies, so Alice can eat:

```python
6 / 2 = 3
```

candies.

The distinct candy types are:

```python
{1, 2, 3}
```

There are exactly `3` types, and Alice can eat `3` candies, so she can eat one candy of each type.

The answer is:

```python
3
```

Example 2:

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

There are `4` candies, so Alice can eat:

```python
4 / 2 = 2
```

candies.

There are `3` distinct types:

```python
{1, 2, 3}
```

But Alice can only eat `2` candies, so she can eat at most `2` different types.

The answer is:

```python
2
```

Example 3:

```python
candyType = [6, 6, 6, 6]
```

Alice can eat `2` candies, but there is only one candy type.

The answer is:

```python
1
```

## First Thought: Count Types

To maximize the number of different types, Alice should avoid eating duplicate types whenever possible.

So the useful information is not the exact count of every type. We only need to know how many different types exist.

For example:

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

has three distinct types:

```python
1, 2, 3
```

Alice can eat three candies, so she can eat one candy of each type.

## Key Insight

There are two upper limits on the answer.

First, Alice cannot eat more different types than the number of candies she eats:

```python
len(candyType) // 2
```

Second, Alice cannot eat more different types than the number of distinct types available:

```python
len(set(candyType))
```

The best possible answer is the smaller of these two values.

So:

```python
answer = min(len(candyType) // 2, len(set(candyType)))
```

## Algorithm

1. Compute the number of candies Alice can eat:
   ```python id="7gwico"
   limit = len(candyType) // 2
   ```

2. Count the number of distinct candy types:
   ```python id="0tlc1b"
   types = len(set(candyType))
   ```

3. Return:
   ```python id="sojxhl"
   min(limit, types)
   ```

## Correctness

Alice eats exactly `len(candyType) // 2` candies. Since each eaten candy can contribute at most one new type, the answer can never be greater than `len(candyType) // 2`.

Also, Alice cannot eat a type that does not exist. Therefore, the answer can never be greater than the number of distinct values in `candyType`.

So the answer is at most:

```python
min(len(candyType) // 2, len(set(candyType)))
```

This upper bound is always achievable.

If there are at least `len(candyType) // 2` distinct types, Alice can choose one candy from that many different types.

If there are fewer than `len(candyType) // 2` distinct types, Alice can choose one candy from every type, then fill the remaining candies with duplicates. The number of different types eaten is then exactly the number of distinct types.

Therefore, the algorithm returns the maximum possible number of different candy types Alice can eat.

## Complexity

Let `n = len(candyType)`.

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Building the set scans the array once |
| Space | `O(n)` | The set may store all candy types |

## Implementation

```python
class Solution:
    def distributeCandies(self, candyType: list[int]) -> int:
        return min(len(candyType) // 2, len(set(candyType)))
```

## Code Explanation

The expression:

```python
len(candyType) // 2
```

is the number of candies Alice is allowed to eat.

The expression:

```python
len(set(candyType))
```

counts how many distinct candy types exist.

Taking the minimum gives the maximum variety Alice can achieve without exceeding the eating limit.

## Counting With Early Stop

We can stop counting once we already have enough distinct types.

```python
class Solution:
    def distributeCandies(self, candyType: list[int]) -> int:
        limit = len(candyType) // 2
        seen = set()

        for candy in candyType:
            seen.add(candy)

            if len(seen) == limit:
                return limit

        return len(seen)
```

This version has the same worst-case complexity, but it can finish earlier when many distinct types appear near the beginning.

## Testing

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

    assert s.distributeCandies([1, 1, 2, 2, 3, 3]) == 3
    assert s.distributeCandies([1, 1, 2, 3]) == 2
    assert s.distributeCandies([6, 6, 6, 6]) == 1
    assert s.distributeCandies([1, 2]) == 1
    assert s.distributeCandies([-1, -1, 0, 1]) == 2
    assert s.distributeCandies([1, 2, 3, 4, 5, 6]) == 3

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `[1, 1, 2, 2, 3, 3]` | Main sample with exactly enough types |
| `[1, 1, 2, 3]` | More types than Alice can eat |
| `[6, 6, 6, 6]` | Only one type exists |
| `[1, 2]` | Small even-length input |
| `[-1, -1, 0, 1]` | Negative candy type values |
| `[1, 2, 3, 4, 5, 6]` | All candies have different types |