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] <= 105In #575 Distribute Candies, you are given an array where each element represents a candy type. The candies are split equally between a brother and sister, and the goal is to maximize the number of distinct candy types the sister receives. Since the total candies are evenly divided, the sister can only receive n / 2 candies.
The key observation is that the sister cannot receive more unique types than the number of candies she gets. Therefore, the result is the minimum between the number of unique candy types and n / 2. A common approach is to use a Hash Set (or hash table) to count distinct candy types efficiently. By inserting each candy type into the set, we can quickly determine how many unique types exist.
This approach works in O(n) time since we scan the array once, and it requires O(n) space for storing unique types. Some alternative solutions sort the array first to count distinct values, but the hash-based method is typically simpler and faster.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash Set (count unique candy types) | O(n) | O(n) |
| Sorting and counting distinct types | O(n log n) | O(1) or O(log n) |
take U forward
Use these hints if you're stuck. Try solving on your own first.
To maximize the number of kinds of candies, we should try to distribute candies such that Alice will gain all kinds.
What is the upper limit of the number of kinds of candies Alice will gain? Remember candies are to distributed equally.
Which data structure is the most suitable for finding the number of kinds of candies?
Will hashset solves the problem? Inserting all candies kind in the hashset and then checking its size with upper limit.
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.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.
1def distributeCandies(candyType):
2 return min(len(set(candyType)), len(candyType) // 2)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.
For another perspective:
n / 2.Time Complexity: O(n) for creating the counter.
Space Complexity: O(n) for storing unique types in the counter.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, problems like Distribute Candies are common in coding interviews because they test understanding of arrays, hash tables, and basic problem reduction. While simple, it evaluates whether candidates can identify constraints and derive an optimal solution.
A hash set is the most suitable data structure because it efficiently tracks unique candy types while iterating through the array. Insert and lookup operations are typically O(1), making the overall algorithm linear in time.
The optimal approach is to count the number of unique candy types using a hash set and compare it with n/2, which is the maximum candies the sister can receive. The answer is the minimum of these two values. This ensures the sister gets the maximum number of distinct candies possible.
The sister can only receive n/2 candies since the candies are split equally. Even if there are more unique candy types, she cannot exceed that limit. Therefore, the maximum distinct candies she can get is the smaller of the unique type count and 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.