Distribute Candies

Easy

Asked by:

8 views

Topics:

Arrays

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 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.length
2 <= n <= 10⁴
n is even.
-10⁵ <= candyType[i] <= 10⁵

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

The problem states that the input array's length, `n`, is always even and at least 2. Should I assume the input will always conform to these rules, or is it better to include validation for an empty or odd-length array?
To ensure I understand the core requirement, a 'type' of candy is simply its integer value, correct? This means `candyType` values like `-5` and `5` would be considered two completely distinct types.
Let's consider the primary constraint: Alice can only eat `n / 2` candies. If the number of unique candy types available is much larger than `n / 2`, the maximum number of types she can eat is capped at `n / 2`. Is this understanding correct?
Conversely, if the number of unique candy types is smaller than `n / 2`, the limiting factor becomes the variety of candies available. In this case, the answer would be the total count of unique types, right?
I notice the candy type values can be negative. Does the sign have any special meaning, or does it simply help define the uniqueness of a candy type?

Brute Force Solution

Approach

The brute force strategy involves systematically creating every possible collection of candies the sister could receive. For each of these collections, we'll count how many unique types of candy she has and then find the highest count from all possibilities.

Here's how the algorithm would work step-by-step:

First, determine the exact number of candies the sister must receive, which is simply half of all the candies.
Next, generate a complete list of every single combination of candies she could be given, making sure each combination has that required number of candies.
Now, examine each of these combinations one by one.
For any given combination, count how many different kinds of candy it contains. For example, two cherry candies and one apple candy count as two different kinds.
Keep track of the highest number of different kinds you have found so far across all the combinations.
After you've looked at every single possible combination, the highest number you've recorded is the answer.

Code Implementation

def distribute_candies_brute_force(candy_type_list):
    import itertools

    # First, determine the exact number of candies the sister can receive as per the rules.
    sister_share_size = len(candy_type_list) // 2

    max_unique_candy_types = 0

    # Systematically generate every possible combination of candies the sister could choose.
    all_possible_combinations = set(itertools.combinations(candy_type_list, sister_share_size))

    # We must check each combination to find the one that maximizes the variety of candies.
    for current_combination in all_possible_combinations:
        unique_candies_in_this_combination = len(set(current_combination))
        
        if unique_candies_in_this_combination > max_unique_candy_types:
            max_unique_candy_types = unique_candies_in_this_combination

    return max_unique_candy_types

Big(O) Analysis

Time Complexity

O(n * C(n, n/2)) – The dominant cost of this brute force approach is generating all possible combinations of candies for the sister. The number of candies she receives is n/2, so we must generate C(n, n/2), or "n choose n/2", combinations. For each of these combinations, we then iterate through its n/2 candies to count the unique types, which takes a time proportional to n. The total number of operations is therefore the product of the number of combinations and the work done for each. This results in an exponential time complexity of O(n * C(n, n/2)).

Space Complexity

O(N * C(N, N/2)) – The primary consumer of auxiliary space is the data structure required to hold "a complete list of every single combination" of candies. Given N total candies, the number of combinations of size N/2 is C(N, N/2), which grows exponentially, and storing all these combinations requires space proportional to N * C(N, N/2). Additionally, a temporary data structure, such as a hash set, is used to count the unique candy types within each combination, consuming up to O(N) space. The memory for the list of all combinations is the dominant factor, leading to an exponential space complexity.

Optimal Solution

Approach

The core idea is to realize that the final answer is limited by one of two factors: either the number of candies Alice is allowed to eat, or the total number of unique candy types she possesses. The solution is simply to find both of these numbers and pick the smaller one.

Here's how the algorithm would work step-by-step:

First, determine the maximum number of candies Alice is allowed to eat. This is simply half of her entire collection.
Next, we need to figure out how many completely different types of candy she has available.
To do this, go through her whole candy collection and make a list of all the unique types, making sure not to count any type more than once.
Imagine you have a display tray. For each candy from her collection, if you haven't seen that type before, place one on the tray.
After checking all of her candies, the number of candies on the display tray represents the total count of distinct candy types.
Finally, compare the number of candies she is allowed to eat with the total count of distinct candy types you found.
The answer is the smaller of these two numbers, as she can't eat more types than she has, nor can she eat more types than her diet allows.

Code Implementation

def distribute_candies(candy_type_list):
    # Using a set is the most direct way to find the count of all distinct candy types.

    number_of_unique_candy_types = len(set(candy_type_list))

    # The problem specifies that the person can only eat n/2 candies, creating a physical limit.

    allowed_candies_to_eat = len(candy_type_list) // 2

    # The answer is the lesser of the two constraints: available variety vs. eating capacity.

    return min(number_of_unique_candy_types, allowed_candies_to_eat)

Big(O) Analysis

Time Complexity

O(n) – Let n be the total number of candies. The dominant cost of this solution is identifying the number of unique candy types. To do this, we must iterate through the entire collection of n candies once. For each candy, we check if we have seen its type before and record it, which is typically an O(1) operation using a hash set. Since we perform a constant-time operation for each of the n candies, the total runtime is directly proportional to n, simplifying to O(n).

Space Complexity

O(N) – The space complexity is driven by the auxiliary data structure used to count unique candy types. The explanation describes creating a 'list of all the unique types' or using a 'display tray' to store each distinct candy type encountered. Let N be the total number of candies in the input collection. In the worst-case scenario, where every candy is of a different type, this structure would need to store N unique elements, making the auxiliary space usage directly proportional to the input size.

Edge Cases

Case	How to Handle
Input array has the minimum possible length, n=2.	The solution correctly calculates Alice can eat 1 candy and returns the minimum of 1 and the number of unique types.
All candies in the input array are of the same type.	The algorithm correctly identifies only one unique type and returns 1, as this is the limiting factor.
All candies in the input array are of different types.	The algorithm correctly determines the limiting factor is the number of candies Alice can eat, n/2, and returns this value.
The number of unique candy types is exactly equal to n/2.	The solution correctly finds that the number of unique types and the number of allowed candies are equal, returning n/2.
Input array has the maximum possible length, n = 10^4.	A hash set-based solution with O(n) time and O(n) space complexity scales efficiently and avoids a timeout or memory error.
Input array contains negative numbers, zero, and values at the integer limits.	A standard hash set handles the full range of specified integer values correctly without any special logic.
The distribution of candy types is highly skewed, with some types appearing many times.	The solution's use of a set correctly counts each candy type only once, regardless of its frequency.
The input array is null, which is outside the problem's constraints.	A production-ready solution would handle this by returning 0, as no candies can be eaten from a non-existent list.

Input array has the minimum possible length, n=2.

How to Handle:

The solution correctly calculates Alice can eat 1 candy and returns the minimum of 1 and the number of unique types.

All candies in the input array are of the same type.

How to Handle:

The algorithm correctly identifies only one unique type and returns 1, as this is the limiting factor.

All candies in the input array are of different types.

How to Handle:

The algorithm correctly determines the limiting factor is the number of candies Alice can eat, n/2, and returns this value.

The number of unique candy types is exactly equal to n/2.

How to Handle:

The solution correctly finds that the number of unique types and the number of allowed candies are equal, returning n/2.

Input array has the maximum possible length, n = 10^4.

How to Handle:

A hash set-based solution with O(n) time and O(n) space complexity scales efficiently and avoids a timeout or memory error.

Input array contains negative numbers, zero, and values at the integer limits.

How to Handle:

A standard hash set handles the full range of specified integer values correctly without any special logic.

The distribution of candy types is highly skewed, with some types appearing many times.

How to Handle:

The solution's use of a set correctly counts each candy type only once, regardless of its frequency.

The input array is null, which is outside the problem's constraints.

How to Handle:

A production-ready solution would handle this by returning 0, as no candies can be eaten from a non-existent list.