LeetCode 575 - Distribute Candies

This problem asks us to maximize the number of distinct candy types Alice can eat while respecting a strict limit on how many candies she is allowed to consume. We are given an integer array candyType, where each element represents the type of a candy.

leetcodeeasyarrayhash-table

LeetCode Problem 575

Difficulty: 🟢 Easy
Topics: Array, Hash Table

Solution

Problem Understanding

This problem asks us to maximize the number of distinct candy types Alice can eat while respecting a strict limit on how many candies she is allowed to consume.

We are given an integer array candyType, where each element represents the type of a candy. Multiple candies may share the same type value. The total number of candies is n, and the problem guarantees that n is always even.

The doctor allows Alice to eat only n / 2 candies. Alice wants as much variety as possible, meaning she wants to maximize the number of different candy types among the candies she chooses to eat.

The key observation is that Alice can eat at most n / 2 candies total, so even if there are many unique candy types available, she cannot eat more than n / 2 distinct types because each distinct type requires at least one candy slot.

At the same time, if there are fewer than n / 2 unique candy types in the entire collection, then the answer is simply the number of unique types available.

Therefore, the answer is:

  • the number of unique candy types
  • capped at n / 2

Mathematically:

answer = min(number_of_unique_types, n / 2)

The constraints are small to moderate:

  • 2 <= n <= 10^4
  • Candy values may be negative or positive
  • n is always even

Since n is only up to 10^4, linear or near-linear solutions are completely acceptable.

Some important edge cases include:

  • All candies are the same type, such as [6,6,6,6]
  • Every candy is a different type
  • The number of unique types is smaller than n / 2
  • The number of unique types is larger than n / 2
  • Negative candy type values

The problem guarantees that the array is non-empty and that n is even, so we do not need special handling for invalid input sizes.

Approaches

Brute Force Approach

A brute-force solution would try every possible subset of size n / 2, then count how many distinct candy types appear in each subset. The maximum distinct count among all subsets would be the answer.

This approach is correct because it explicitly examines every valid selection Alice could make. However, it is computationally infeasible.

If there are n candies, the number of subsets of size n / 2 is:

C(n, n/2)

This grows exponentially and becomes enormous even for moderate values of n.

For example:

C(30,15) = 155,117,520

Trying all combinations would be far too slow.

Optimal Approach

The important insight is that we do not actually need to determine which candies Alice eats. We only need to know the maximum possible number of distinct types.

There are two limiting factors:

  1. Alice can eat only n / 2 candies total.
  2. Alice cannot eat more distinct types than actually exist.

So if:

  • there are k unique candy types
  • Alice may eat n / 2 candies

then the maximum distinct types she can eat is:

min(k, n / 2)

A hash set is ideal here because it automatically stores only unique values.

We:

  1. Insert all candy types into a set
  2. Count the number of unique types
  3. Return the minimum of:
  • unique count
  • n / 2

This gives a clean linear-time solution.

Approach Time Complexity Space Complexity Notes
Brute Force O(C(n, n/2) * n) O(n) Tries every possible candy selection
Optimal O(n) O(n) Uses a hash set to count unique candy types

Algorithm Walkthrough

  1. Compute how many candies Alice is allowed to eat.

Since the total number of candies is n, Alice may eat:

n / 2

candies. 2. Create a hash set containing all candy types.

A hash set automatically removes duplicates, so after inserting all values, the size of the set equals the number of distinct candy types. 3. Count the number of unique candy types.

This is simply:

len(unique_types)

in Python, or len(map) in Go. 4. Return the smaller value between:

  • the number of unique types
  • the allowed candy count

Alice cannot eat more than n / 2 candies total, so even if there are more unique types available, she is limited by the number of candies she may consume.

Why it works

The algorithm works because every distinct candy type requires at least one candy to be eaten. Therefore, Alice can never eat more than n / 2 distinct types.

At the same time, Alice also cannot eat more distinct types than actually exist in the collection.

So the true maximum must be the smaller of:

  • the total unique candy types
  • the allowed number of candies

This guarantees correctness.

Python Solution

from typing import List

class Solution:
    def distributeCandies(self, candyType: List[int]) -> int:
        unique_types = set(candyType)
        max_allowed = len(candyType) // 2

        return min(len(unique_types), max_allowed)

The implementation is very compact because Python's built-in set type directly supports the operation we need.

First, we convert the input array into a set. This removes duplicate candy types automatically.

Next, we compute how many candies Alice is allowed to eat, which is half the array length.

Finally, we return the smaller value between:

  • the number of unique candy types
  • the maximum number of candies Alice may eat

This directly matches the mathematical observation derived earlier.

Go Solution

func distributeCandies(candyType []int) int {
    uniqueTypes := make(map[int]bool)

    for _, candy := range candyType {
        uniqueTypes[candy] = true
    }

    maxAllowed := len(candyType) / 2
    uniqueCount := len(uniqueTypes)

    if uniqueCount < maxAllowed {
        return uniqueCount
    }

    return maxAllowed
}

The Go version uses a map to simulate a hash set because Go does not provide a built-in set type.

The map keys represent candy types, and the boolean values are placeholders.

After inserting all candy types into the map, the number of keys equals the number of unique candy types.

Unlike Python, Go does not have a built-in min function for integers, so we use a simple conditional check to return the smaller value.

Worked Examples

Example 1

Input: [1,1,2,2,3,3]

Alice has:

n = 6

She may eat:

6 / 2 = 3

candies.

Step-by-step state

Step Candy Unique Set
1 1 {1}
2 1 {1}
3 2 {1,2}
4 2 {1,2}
5 3 {1,2,3}
6 3 {1,2,3}

Unique types:

3

Maximum allowed candies:

3

Result:

min(3, 3) = 3

Example 2

Input: [1,1,2,3]

Alice has:

n = 4

She may eat:

2

candies.

Step-by-step state

Step Candy Unique Set
1 1 {1}
2 1 {1}
3 2 {1,2}
4 3 {1,2,3}

Unique types:

3

Maximum allowed candies:

2

Result:

min(3, 2) = 2

Example 3

Input: [6,6,6,6]

Alice has:

n = 4

She may eat:

2

candies.

Step-by-step state

Step Candy Unique Set
1 6 {6}
2 6 {6}
3 6 {6}
4 6 {6}

Unique types:

1

Maximum allowed candies:

2

Result:

min(1, 2) = 1

Complexity Analysis

Measure Complexity Explanation
Time O(n) We iterate through the array once
Space O(n) The hash set may store all candy types

The time complexity is linear because each candy is inserted into the hash set exactly once. Hash set insertion is average-case O(1), so processing all n candies costs O(n).

The space complexity is also O(n) in the worst case, when every candy type is unique and all elements must be stored in the set.

Test Cases

solution = Solution()

assert solution.distributeCandies([1,1,2,2,3,3]) == 3  # Example 1
assert solution.distributeCandies([1,1,2,3]) == 2      # Example 2
assert solution.distributeCandies([6,6,6,6]) == 1      # Example 3

assert solution.distributeCandies([1,2]) == 1          # Minimum valid input
assert solution.distributeCandies([1,2,3,4]) == 2      # All unique types
assert solution.distributeCandies([1,1,1,1,2,2]) == 2  # Fewer unique types than limit
assert solution.distributeCandies([1,2,3,4,5,6]) == 3  # More unique types than limit
assert solution.distributeCandies([-1,-1,-2,-3]) == 2  # Negative candy types
assert solution.distributeCandies([0,0,0,1,2,3]) == 3  # Mix of duplicates and uniques
assert solution.distributeCandies([5,5,5,5,5,5]) == 1  # Single unique type
Test Why
[1,1,2,2,3,3] Standard balanced example
[1,1,2,3] Unique count exceeds allowed candies
[6,6,6,6] Only one candy type exists
[1,2] Smallest valid input size
[1,2,3,4] Every candy is unique
[1,1,1,1,2,2] Unique count smaller than eating limit
[1,2,3,4,5,6] Unique count larger than eating limit
[-1,-1,-2,-3] Confirms negative values work correctly
[0,0,0,1,2,3] Combination of duplicates and unique values
[5,5,5,5,5,5] Extreme duplicate-heavy case

Edge Cases

One important edge case occurs when all candies are the same type. For example:

[6,6,6,6]

Alice may eat two candies, but there is only one distinct type available. A buggy solution might incorrectly return 2 by assuming Alice can always eat n / 2 distinct candies. Our implementation correctly handles this because the set size is 1, and we return the minimum between 1 and 2.

Another important case is when every candy is unique. For example:

[1,2,3,4,5,6]

There are six distinct types, but Alice may eat only three candies. A naive implementation might mistakenly return all six unique types. Our solution correctly caps the answer at n / 2.

A third edge case involves negative candy type values. The constraints allow values from -10^5 to 10^5. Some incorrect implementations may assume candy types are non-negative and attempt array indexing. Our solution uses a hash set, so negative values work naturally without any special handling.

A final edge case is the minimum input size:

[1,2]

Alice may eat only one candy. Even though there are two distinct types, the answer must be 1. The formula min(unique_types, n / 2) handles this correctly and consistently.