Leetcode – Distribute Candies Solution in Python

Spread the love

“Distribute Candies” is a thought-provoking problem found on Leetcode that evaluates your problem-solving skills and understanding of hash maps. This article aims to provide an in-depth exploration of the problem, discuss different strategies to tackle it, and illustrate the solutions using Python code.

Problem Statement

The problem (#575 on Leetcode) is titled “Distribute Candies” and the problem statement is as follows:

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 eat n / 2 size of candy a day. Alice likes this new diet and will follow it. The doctor advised her to eat only one type of candy each day.

Return the maximum number of different types of candies Alice can eat if she only eats n / 2 size of candies a day.

Example:

Input: candyType = [1,1,2,2,3,3]
Output: 3
Explanation: Alice can only eat 6 / 2 = 3 candies a day.
If Alice eats one candy of each type the maximum number of days she can eat is 3 days.

Approaches to Solve the Problem

1. Using Set Data Structure

The first approach is quite simple and utilizes a set to count the distinct types of candies. Alice can eat a maximum of n/2 candies. If the number of unique candies is greater than or equal to n/2, she can eat different candies every day. Otherwise, she will eventually have to eat some type of candy more than once.

def distributeCandies(candyType):
    # Count the distinct types of candies using a set
    unique_candies = len(set(candyType))
    
    # Alice can eat n/2 candies
    max_candies = len(candyType) // 2
    
    # The maximum number of different candies Alice can eat is the minimum of unique candies and n/2
    return min(unique_candies, max_candies)

Explanation:

  1. Calculate the number of unique candy types using a set.
  2. Alice can eat n/2 candies.
  3. The answer is the minimum between the number of unique candies and n/2.

Time Complexity:

The time complexity of this approach is O(n) where n is the number of candies, as we need to traverse the entire list once. The space complexity is also O(n) in the worst case, as we might store all candies in the set.

2. Optimizing Space by Early Stopping

We can optimize the space by stopping early when we find that the number of unique candies is already equal to n/2. There’s no need to continue counting past this point since Alice can’t eat more than n/2 candies.

def distributeCandies(candyType):
    unique_candies = set()
    max_candies = len(candyType) // 2
    
    for candy in candyType:
        unique_candies.add(candy)
        
        # If the number of unique candies reaches n/2, we can stop early
        if len(unique_candies) == max_candies:
            return max_candies
    
    # If we reach here, the number of unique candies is less than n/2
    return len(unique_candies)

Explanation:

  1. We keep a set to count unique candy types.
  2. We iterate through each candy and add it to the set. If at any point, the size of the set becomes equal to n/2, we can stop and return n/2.
  3. If the loop completes, it means the number of unique candies is less than n/2, and we return the size of the set.

Time Complexity:

The time complexity remains O(n), but this approach can have an early stopping condition which potentially reduces the number of iterations. The space complexity is O(n) in the worst case but could be less due to early stopping.

Conclusion

The “Distribute Candies” problem is an engaging problem that tests your ability to analyze and solve optimization problems efficiently. We explored two solutions in Python, one that uses a set to find unique candy types and another that optimizes space by using an early stopping condition.

Leave a Reply