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

Example function shape:

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

Examples

Example 1:

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

There are 6 candies, so Alice can eat:

6 / 2 = 3

candies.

The distinct candy types are:

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

3

Example 2:

candyType = [1, 1, 2, 3]

There are 4 candies, so Alice can eat:

4 / 2 = 2

candies.

There are 3 distinct types:

{1, 2, 3}

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

The answer is:

2

Example 3:

candyType = [6, 6, 6, 6]

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

The answer is:

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:

[1, 1, 1, 1, 2, 3]

has three distinct types:

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:

len(candyType) // 2

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

len(set(candyType))

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

So:

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

Algorithm

1. Compute the number of candies Alice can eat:

   limit = len(candyType) // 2

2. Count the number of distinct candy types:

   types = len(set(candyType))

3. Return:

   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:

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).

Implementation

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

Code Explanation

The expression:

len(candyType) // 2

is the number of candies Alice is allowed to eat.

The expression:

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.

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

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()