Distribute Candies
EasyPrompt
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 <= 104nis even.-105 <= candyType[i] <= 105
Approaches
3 approaches with complexity analysis and trade-offs.
This approach uses a brute-force method to find the number of unique candy types. It iterates through the array of candies and, for each candy, checks if it has been seen before by searching through a list of unique types found so far. If it's a new type, it's added to the list.
Algorithm
- Calculate the maximum number of candies Alice can eat, which is
n / 2. - Initialize an empty list,
uniqueTypes, to store the unique candy types found. - Iterate through each
candyin thecandyTypearray. - For each
candy, perform a linear search on theuniqueTypeslist to check if it's already present. - If the
candyis not in the list, add it. - After iterating through all candies, the number of unique types is the size of the
uniqueTypeslist. - The result is the minimum of the number of unique types and the number of candies Alice is allowed to eat.
Walkthrough
We start by calculating the maximum number of candies Alice is allowed to eat, which is half the total number of candies (n / 2). We then create a dynamic list, like an ArrayList in Java, to keep track of the unique candy types we encounter. We loop through the input candyType array one candy at a time. For each candy, we check if this type is already in our list of unique types. This check involves iterating through the list of unique types found so far. If the current candy type is not found, we add it to our list. After checking all the candies, the size of our uniqueTypes list gives the total count of distinct candy types. Finally, Alice can eat at most n / 2 candies, so the maximum number of different types she can eat is the smaller of the two values: the total number of unique types available and n / 2.
import java.util.ArrayList;import java.util.List; class Solution { public int distributeCandies(int[] candyType) { int n = candyType.length; int maxAllowed = n / 2; List<Integer> uniqueTypes = new ArrayList<>(); for (int candy : candyType) { if (!uniqueTypes.contains(candy)) { uniqueTypes.add(candy); } } int numUniqueTypes = uniqueTypes.size(); return Math.min(numUniqueTypes, maxAllowed); }}Complexity
Time
O(n^2). The outer loop runs `n` times. For each element, `list.contains()` performs a linear scan, which takes O(k) time, where `k` is the current number of unique elements. In the worst case, `k` can be up to `n`, leading to a total time complexity of O(n^2).
Space
O(k), where `k` is the number of unique candy types. In the worst case, all candies are unique, so the space complexity is O(n) to store the unique types in the list.
Trade-offs
Pros
Conceptually simple and easy to implement without requiring knowledge of advanced data structures.
Cons
Highly inefficient for large inputs due to its O(n^2) time complexity.
The
containscheck on anArrayListis slow.
A more optimized approach involves sorting the candyType array first. Once sorted, all candies of the same type will be adjacent to each other. This makes it easy to count the number of unique types by iterating through the sorted array just once.
Algorithm
- Calculate the maximum number of candies Alice can eat:
maxAllowed = candyType.length / 2. - Sort the
candyTypearray in non-decreasing order. - Initialize a counter for unique types,
uniqueCount, to 1 (since the first element is always a unique type). - Iterate through the sorted array from the second element (
i = 1ton-1). - Compare the current element
candyType[i]with the previous elementcandyType[i-1]. - If they are different, it signifies a new unique type, so increment
uniqueCount. - After the loop,
uniqueCountholds the total number of distinct candy types. - Return
Math.min(uniqueCount, maxAllowed).
Walkthrough
The main idea here is to leverage sorting to group identical elements together. By sorting the candyType array, we ensure that all occurrences of a specific candy type are contiguous. After sorting, we can find the number of unique types by simply iterating through the array and counting how many times the value changes. We initialize a counter for unique types to 1 (to account for the first type). Then, we loop from the second element to the end of the array. In each step, we compare the current candy with the previous one. If candyType[i] is different from candyType[i-1], we have found a new unique type and increment our counter. After this single pass, we have the total count of unique candy types. The final answer is the minimum of this count and the number of candies Alice is allowed to eat (n / 2).
import java.util.Arrays; class Solution { public int distributeCandies(int[] candyType) { int n = candyType.length; int maxAllowed = n / 2; Arrays.sort(candyType); int uniqueCount = 1; for (int i = 1; i < n; i++) { if (candyType[i] != candyType[i - 1]) { uniqueCount++; } } return Math.min(uniqueCount, maxAllowed); }}Complexity
Time
O(n log n). The dominant part of this approach is the sorting step, which typically has a time complexity of O(n log n). The subsequent linear scan to count unique elements takes O(n) time, which is subsumed by the sorting time.
Space
O(log n) to O(n). The space complexity depends on the implementation of the sorting algorithm. In Java, `Arrays.sort()` for primitive types uses a dual-pivot Quicksort, which requires O(log n) space on average for the recursion stack, but can be O(n) in the worst case.
Trade-offs
Pros
Much more efficient than the brute-force approach.
Requires minimal extra space if an in-place sorting algorithm is used.
Cons
Slower than the optimal hash set approach.
Sorting the array modifies the input array, which might not be desirable in some contexts. A copy would be needed to avoid this, costing extra space.
The most efficient approach uses a HashSet data structure. A hash set is ideal for this problem because it only stores unique elements and provides, on average, constant time complexity for adding elements. By iterating through the candies and adding them to a set, we can quickly find the number of unique types.
Algorithm
- Calculate the maximum number of candies Alice can eat:
maxAllowed = candyType.length / 2. - Create an empty
HashSetto store the types of candies. - Iterate through each
candyin thecandyTypearray. - For each
candy, add it to theHashSet. The set will automatically handle duplicates, ensuring only unique types are stored. - After the loop, the number of unique candy types is simply the size of the
HashSet. - Return the minimum of the set's size and
maxAllowed.
Walkthrough
This approach leverages the properties of a HashSet to efficiently count unique elements. We initialize an empty HashSet. Then, we iterate through the candyType array. For each candy, we attempt to add it to the set. The add operation of a HashSet will only succeed if the element is not already present, thus automatically filtering out duplicates. This process takes, on average, O(1) time for each candy. After iterating through all the candies, the size() of the HashSet gives us the exact number of distinct candy types. As before, the maximum number of different types Alice can eat is limited by the number of candies she is allowed to eat (n / 2). Therefore, the answer is the minimum of the number of unique types (the set's size) and n / 2.
import java.util.HashSet;import java.util.Set; class Solution { public int distributeCandies(int[] candyType) { int n = candyType.length; int maxAllowed = n / 2; Set<Integer> uniqueTypes = new HashSet<>(); for (int candy : candyType) { uniqueTypes.add(candy); } return Math.min(uniqueTypes.size(), maxAllowed); }}Complexity
Time
O(n). We iterate through the `candyType` array of length `n` once. Adding an element to a `HashSet` takes O(1) time on average. Thus, the total time complexity is linear with respect to the number of candies.
Space
O(k), where `k` is the number of unique candy types. In the worst case, all `n` candies are of different types, so the space complexity becomes O(n) to store them in the set.
Trade-offs
Pros
Optimal time complexity of O(n).
The code is concise and clearly expresses the intent of finding unique items.
Cons
Requires extra space to store the hash set, which can be up to O(n) in the worst case where all candies are unique.
Solutions
Solution
class Solution {public int distributeCandies(int[] candyType) { Set<Integer> s = new HashSet<>(); for (int c : candyType) { s.add(c); } return Math.min(candyType.length >> 1, s.size()); }}class Solution {public: int distributeCandies(vector<int> &candyType) { unordered_set<int> s; for (int c : candyType) s.insert(c); return min(candyType.size() >> 1, s.size()); }};class Solution: def distributeCandies( self, candyType: List[int]) -> int: return min(len(candyType) >> 1, len(set(candyType)))Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.