Distribute Candies

Difficulty: Easy | Acceptance: 71.10% | Paid: No Topics: Array, Hash Table

Alice has n candies, where the i-th 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.

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.

• Examples
• Constraints
• Hash Set
• Sorting
• Boolean Array

Examples

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 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. Since there is only 1 type, she can only eat 2 candies of that type.

Constraints

- n == candyType.length
- 2 <= n <= 10^4
- n is even.
- -10^5 <= candyType[i] <= 10^5

Hash Set

Intuition To find the maximum number of different types of candies Alice can eat, we first need to know how many unique types of candies exist in the array. A Hash Set is the ideal data structure for this because it stores unique elements and provides O(1) average time complexity for insertions and lookups.

Steps

• Initialize an empty Hash Set.
• Iterate through the candyType array and add each candy type to the set. The set will automatically handle duplicates, storing only unique types.
• The size of the set represents the total number of unique candy types available.
• Alice can eat at most n / 2 candies. Therefore, the answer is the minimum of the number of unique types (set size) and n / 2.

class Solution:
    def distributeCandies(self, candyType: list[int]) -> int:
        # Calculate the number of unique candy types using a set
        unique_types = len(set(candyType))
        # Alice can only eat n / 2 candies
        max_eat = len(candyType) // 2
        # The answer is the smaller of the two
        return min(unique_types, max_eat)

Complexity

• Time: O(N), where N is the number of candies. We iterate through the array once, and set insertions are O(1) on average.
• Space: O(N), to store the unique candy types in the set. In the worst case (all candies are unique), the set size is N.
• Notes: This is the most straightforward and generally preferred approach due to its linear time complexity.

Sorting

Intuition If we sort the array, identical candy types will be grouped together in adjacent positions. We can then iterate through the sorted array and count how many times the type changes from one element to the next. This count gives us the number of unique types.

Steps

• Sort the candyType array in ascending order.
• Initialize a counter for unique types to 1 (since a sorted array with at least one element has at least one type, or handle empty array edge case if applicable, though constraints say n >= 2).
• Iterate through the array starting from the second element. If the current element is different from the previous element, increment the unique type counter.
• The result is the minimum of the unique type counter and n / 2.

class Solution:
    def distributeCandies(self, candyType: list[int]) -> int:
        # Sort the array to group identical types
        candyType.sort()
        
        # Count unique types by checking adjacent elements
        unique_count = 1
        for i in range(1, len(candyType)):
            if candyType[i] != candyType[i - 1]:
                unique_count += 1
                
        # Return the minimum of unique types and n/2
        return min(unique_count, len(candyType) // 2)

Complexity

• Time: O(N log N), due to the sorting step. The iteration is O(N).
• Space: O(1) or O(N), depending on the sorting algorithm’s implementation (e.g., heapsort uses O(1), quicksort O(log N) stack space, Timsort O(N)).
• Notes: This approach is useful if modifying the input array is allowed and memory space is extremely constrained (though the Hash Set approach is generally faster).

Boolean Array

Intuition The problem constraints state that candyType[i] is between -100,000 and 100,000. This is a relatively small fixed range. We can use a boolean array (or a bitset) of size 200,001 to map each possible candy type to a boolean flag indicating whether we have seen it.

Steps

• Create a boolean array seen of size 200,001 (to cover the range -100,000 to 100,000).
• Initialize a counter for unique types to 0.
• Iterate through candyType. For each candy, calculate its index in the seen array by adding an offset of 100,000 (to handle negative indices).
• If seen[index] is false, set it to true and increment the unique counter.
• The result is the minimum of the unique counter and n / 2.

class Solution:
    def distributeCandies(self, candyType: list[int]) -> int:
        # Offset to handle negative indices (range -100,000 to 100,000)
        OFFSET = 100000
        # Boolean array to track seen types
        seen = [False] * 200001
        unique_count = 0
        
        for candy in candyType:
            idx = candy + OFFSET
            if not seen[idx]:
                seen[idx] = True
                unique_count += 1
                
        return min(unique_count, len(candyType) // 2)

Complexity

• Time: O(N), where N is the number of candies. We iterate through the array once, and array access is O(1).
• Space: O(1), because the size of the boolean array is fixed (200,001) regardless of the input size N. It does not scale with N.
• Notes: This is a very efficient approach in terms of both time and space when the range of values is known and small.