Alice has n candies, where the ith candy is of type candyType[i]. Alice noticed that she started to gain weight, so she visited a doctor.
The doctor advised Alice to only eat n / 2 of the candies she has (n is always even). Alice likes her candies very much, and she wants to eat the maximum number of different types of candies while still following the doctor's advice.
Given the integer array candyType of length n, return the maximum number of different types of candies she can eat if she only eats n / 2 of them.
Example 1:
Input: candyType = [1,1,2,2,3,3] Output: 3 Explanation: Alice can only eat 6 / 2 = 3 candies. Since there are only 3 types, she can eat one of each type.
Example 2:
Input: candyType = [1,1,2,3] Output: 2 Explanation: Alice can only eat 4 / 2 = 2 candies. Whether she eats types [1,2], [1,3], or [2,3], she still can only eat 2 different types.
Example 3:
Input: candyType = [6,6,6,6] Output: 1 Explanation: Alice can only eat 4 / 2 = 2 candies. Even though she can eat 2 candies, she only has 1 type.
Constraints:
n == candyType.length2 <= n <= 104n is even.-105 <= candyType[i] <= 105Problem Overview: You receive an array where each value represents a candy type. Alice must eat exactly n/2 candies from the array. The goal is to maximize the number of different types she eats. The key observation: Alice cannot eat more than n/2 candies, but she also cannot exceed the total number of unique candy types available.
This problem sits at the intersection of Array traversal and counting unique elements using a Hash Table. Once you recognize the constraint n/2, the solution becomes a simple comparison between the number of unique candy types and the maximum candies Alice can eat.
Approach 1: Using Sets for Unique Types (O(n) time, O(n) space)
Insert every candy type into a set. A set automatically removes duplicates, leaving only the unique candy types. Let uniqueTypes be the size of this set and limit = n / 2. Alice can eat at most limit candies, so the maximum distinct types she can eat is min(uniqueTypes, limit). The algorithm iterates once through the array to build the set and then returns this minimum value. This approach is clean and relies on constant-time hash insertions.
This is usually the first solution engineers write during interviews because it maps directly to the problem statement: count unique values and compare them with the allowed number of candies.
Approach 2: Frequency Map and Counting (O(n) time, O(n) space)
Instead of a set, build a frequency map using a hash table. Iterate through the array and increment the count for each candy type. The number of keys in the map represents the number of unique candy types. Once the map is built, compute limit = n / 2 and return min(number_of_keys, limit). The frequency values themselves are not strictly required for this problem, but constructing the map demonstrates how duplicate tracking works in many counting problems.
This approach is slightly more verbose than the set solution but useful if you later extend the problem to require counts or additional constraints.
Recommended for interviews: The set-based solution is the expected answer. It shows you immediately recognize the constraint that Alice can eat only n/2 candies and that the problem reduces to counting unique types. Interviewers usually want to see the reasoning: maxDistinct = min(uniqueTypes, n/2). Mentioning the frequency map alternative also demonstrates familiarity with common hash table counting patterns.
The goal is to find the maximum number of unique types of candies Alice can eat. We can take the following steps:
maxCandies = n / 2.maxCandies.This solution creates a set from the list of candies to determine how many unique types there are. The minimum of the number of unique types and n / 2 candies Alice can eat is the answer.
Time Complexity: O(n) because we iterate over the array to create the set.
Space Complexity: O(n) for storing the unique types in a set.
For another perspective:
n / 2.This python solution uses Counter to determine frequency counts, which inherently provides unique element counts. The minimal value between this count and n / 2 determines how many types Alice can eat.
Time Complexity: O(n) for creating the counter.
Space Complexity: O(n) for storing unique types in the counter.
We use a hash table to store the types of candies. If the number of candy types is less than n / 2, then the maximum number of candy types that Alice can eat is the number of candy types. Otherwise, the maximum number of candy types that Alice can eat is n / 2.
The time complexity is O(n), and the space complexity is O(n). Where n is the number of candies.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Using Sets for Unique Types | Time Complexity: O(n) because we iterate over the array to create the set. |
| Approach 2: Frequency Map and Counting | Time Complexity: O(n) for creating the counter. |
| Hash Table | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Using Set for Unique Types | O(n) | O(n) | Best general solution. Quickly counts unique candy types with minimal code. |
| Frequency Map and Counting | O(n) | O(n) | Useful when you also need counts of each candy type or when extending the problem. |
Distribute Candies | Live Coding with Explanation | Leetcode - 575 • Algorithms Made Easy • 5,070 views views
Watch 9 more video solutions →Practice Distribute Candies with our built-in code editor and test cases.
Practice on FleetCode