#575

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Distribute Candies

Maximize the number of different candies Alice can eat given a set of candies and constraints on quantity.

Problem Statement

Alice has n candies, represented by an integer array candyType, where candyType[i] is the type of the ith candy. Alice's doctor recommends that she only eat n / 2 candies to avoid gaining weight. She wants to eat the maximum number of different types of candies while following the doctor's advice.

Given the array candyType, your task is to determine the maximum number of different types of candies Alice can eat if she only consumes n / 2 of them. The number of candies she can eat is fixed, but the variety of types she can enjoy depends on the uniqueness of the types in the array.

Examples

Example 1

Input: candyType = [1,1,2,2,3,3]

Output: 3

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

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

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 <= 104
n is even.
-105 <= candyType[i] <= 105

Solution Approach

Count Unique Types

By scanning through the candyType array, we can determine the number of unique candy types by adding them to a set or hash table. This helps to know how many distinct types are available for Alice to eat.

Consider Limits

Alice can only eat n / 2 candies, so we need to consider the smaller of the total number of unique candy types or n / 2. This will give us the maximum variety Alice can consume without exceeding the recommended limit.

Return Result

The result is simply the smaller value between the count of unique candy types and n / 2, as Alice can only eat that many different types based on the constraints.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of the solution is O(n) due to the need to scan through the array to collect unique candy types, where n is the length of candyType. The space complexity is O(n) for storing the unique types, as we use a set or hash table to track them.

What Interviewers Usually Probe

Candidate should efficiently use hash lookup or set operations to track unique candy types.
Look for clarity in explaining the decision-making process between total unique types and n / 2 limit.
Verify that the candidate handles edge cases like arrays with one type of candy.

Common Pitfalls or Variants

Common pitfalls

Failing to correctly identify the unique types by not using a hash set or similar structure.
Not handling the case where the number of unique candy types is less than n / 2, which could lead to an incorrect result.
Overcomplicating the solution by attempting unnecessary optimizations or algorithms.

Follow-up variants

What if Alice had to eat a fixed number of candies, regardless of type?
What if candyType had no duplicates, and Alice needed to eat as many different types as possible?
What if the problem constraints changed and n was no longer even?

FAQ

What is the main algorithmic pattern used in this problem?

The problem relies on array scanning combined with hash lookup to count unique candy types efficiently.

How do we ensure Alice eats as many different types as possible?

We ensure this by counting the unique candy types and comparing it with n / 2, choosing the smaller value.

What is the time complexity of the solution?

The time complexity is O(n), as we only need to scan through the array once to count unique types.

What is the space complexity of this solution?

The space complexity is O(n), as we need a set or hash table to store unique candy types.

How can this problem be modified in a real-world interview?

The problem could involve additional constraints like limiting the total number of candies Alice can consume or different ways to calculate the number of candies she can eat.

terminal

Solution

Solution 1: Hash Table

We use a hash table to store the types of candies. If the number of candy types is less than $n / 2$, then the maximum number of candy types that Alice can eat is the number of candy types. Otherwise, the maximum number of candy types that Alice can eat is $n / 2$.

1

2

3

class Solution:
    def distributeCandies(self, candyType: List[int]) -> int:
        return min(len(candyType) >> 1, len(set(candyType)))

Continue Practicing

#560 subarray sum equals k #594 longest harmonious subsequence #554 brick wall