Problem Description

You are given an array candyType where each element represents a type of candy. There are n candies in total, and n is always even. Your task is to distribute the candies equally between a brother and a sister. The goal is to maximize the number of different types of candies that the sister can get, assuming she can only get n / 2 candies.

Important constraints:

• Each candy can only be given to one person (no sharing or splitting candies).
• The sister can get at most n / 2 candies.
• You want to maximize the number of unique candy types the sister receives.

Thought Process

At first glance, it might seem like we need to carefully select which candies to give to the sister to maximize her unique types. A brute-force approach would be to try all combinations of n / 2 candies and count the unique types for each, but this would be very inefficient.

Upon closer examination, we realize that the maximum number of unique candies the sister can get is limited by two things:

• The number of candies she can take (n / 2).
• The total number of unique candy types available.

Solution Approach

Let's break down the steps to solve this problem efficiently:

1. Count the unique candy types:
   • We can use a set (or hash map) to store each unique type as we iterate through the array.
2. Calculate the maximum candies the sister can take:
   • This is simply n / 2, where n is the length of candyType.
3. Return the minimum of the two numbers:
   • This ensures we do not exceed either the number of unique types or the allowed number of candies.

We use a set because it provides O(1) lookup and insertion time, making it efficient for counting unique elements.

Example Walkthrough

Suppose candyType = [1, 1, 2, 2, 3, 3].

• Total candies, n = 6.
• The sister can get n / 2 = 3 candies.
• Unique types: {1, 2, 3} → 3 unique types.
• The minimum of 3 (unique types) and 3 (candies she can take) is 3.

So, the sister can get all 3 unique types if she picks one of each type.

Let's try another example: candyType = [1, 1, 2, 3]

• Total candies, n = 4.
• The sister can get n / 2 = 2 candies.
• Unique types: {1, 2, 3} → 3 unique types.
• The minimum of 3 (unique types) and 2 (candies she can take) is 2.

She can only get 2 unique types, since she can only take 2 candies.

Time and Space Complexity

Brute-force approach:

• Would involve generating all combinations of n/2 candies and counting the unique types for each.
• The number of combinations is very large: C(n, n/2), which is exponential.
• Time complexity: O(2^n) — not practical for large n.

• We only need to iterate through the array once to collect unique types: O(n).
• Calculating n/2 and taking the minimum is O(1).
• Space complexity: O(k), where k is the number of unique types (at most n if all are unique).

Thus, the efficient solution is O(n) time and O(k) space.

Summary

The key insight is that the sister's maximum number of unique candies is limited by both the number of candies she can take and the number of unique types available. By using a set to count unique types, we achieve an efficient O(n) solution. This approach is both simple and elegant, avoiding unnecessary complexity and brute-force enumeration.

Code Implementation

class Solution:
    def distributeCandies(self, candyType):
        unique_types = set(candyType)
        max_candies = len(candyType) // 2
        return min(len(unique_types), max_candies)
      

class Solution {
public:
    int distributeCandies(vector<int>& candyType) {
        unordered_set<int> unique_types(candyType.begin(), candyType.end());
        int max_candies = candyType.size() / 2;
        return min((int)unique_types.size(), max_candies);
    }
};
      

import java.util.HashSet;

class Solution {
    public int distributeCandies(int[] candyType) {
        HashSet<Integer> uniqueTypes = new HashSet<>();
        for (int t : candyType) {
            uniqueTypes.add(t);
        }
        int maxCandies = candyType.length / 2;
        return Math.min(uniqueTypes.size(), maxCandies);
    }
}
      

var distributeCandies = function(candyType) {
    const uniqueTypes = new Set(candyType);
    const maxCandies = candyType.length / 2;
    return Math.min(uniqueTypes.size, maxCandies);
};