# Distribute Candies
**Difficulty:** EASY
[External](https://leetcode.com/problems/distribute-candies)
Canonical: https://scaleengineer.com/dsa/problems/distribute-candies
**Data structures:** Array, Hash Table
**Companies:** [LiveRamp](https://scaleengineer.com/companies/liveramp)
---
## Problem
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 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 <= 104`
* `n` is even.
* `-105 <= candyType[i] <= 105`

# Approaches
## Brute Force with Nested Loops
This approach uses a brute-force method to find the number of unique candy types. It iterates through the array of candies and, for each candy, checks if it has been seen before by searching through a list of unique types found so far. If it's a new type, it's added to the list.
**Time:** O(n^2). The outer loop runs `n` times. For each element, `list.contains()` performs a linear scan, which takes O(k) time, where `k` is the current number of unique elements. In the worst case, `k` can be up to `n`, leading to a total time complexity of O(n^2). · **Space:** O(k), where `k` is the number of unique candy types. In the worst case, all candies are unique, so the space complexity is O(n) to store the unique types in the list.
**Pros:** Conceptually simple and easy to implement without requiring knowledge of advanced data structures.
**Cons:** Highly inefficient for large inputs due to its O(n^2) time complexity.; The `contains` check on an `ArrayList` is slow.
### Explanation
We start by calculating the maximum number of candies Alice is allowed to eat, which is half the total number of candies (`n / 2`). We then create a dynamic list, like an `ArrayList` in Java, to keep track of the unique candy types we encounter. We loop through the input `candyType` array one candy at a time. For each candy, we check if this type is already in our list of unique types. This check involves iterating through the list of unique types found so far. If the current candy type is not found, we add it to our list. After checking all the candies, the size of our `uniqueTypes` list gives the total count of distinct candy types. Finally, Alice can eat at most `n / 2` candies, so the maximum number of *different* types she can eat is the smaller of the two values: the total number of unique types available and `n / 2`.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int distributeCandies(int[] candyType) {
        int n = candyType.length;
        int maxAllowed = n / 2;

        List<Integer> uniqueTypes = new ArrayList<>();
        for (int candy : candyType) {
            if (!uniqueTypes.contains(candy)) {
                uniqueTypes.add(candy);
            }
        }

        int numUniqueTypes = uniqueTypes.size();
        return Math.min(numUniqueTypes, maxAllowed);
    }
}
```
### Algorithm
- Calculate the maximum number of candies Alice can eat, which is `n / 2`.
- Initialize an empty list, `uniqueTypes`, to store the unique candy types found.
- Iterate through each `candy` in the `candyType` array.
- For each `candy`, perform a linear search on the `uniqueTypes` list to check if it's already present.
- If the `candy` is not in the list, add it.
- After iterating through all candies, the number of unique types is the size of the `uniqueTypes` list.
- The result is the minimum of the number of unique types and the number of candies Alice is allowed to eat.

## Sorting Approach
A more optimized approach involves sorting the `candyType` array first. Once sorted, all candies of the same type will be adjacent to each other. This makes it easy to count the number of unique types by iterating through the sorted array just once.
**Time:** O(n log n). The dominant part of this approach is the sorting step, which typically has a time complexity of O(n log n). The subsequent linear scan to count unique elements takes O(n) time, which is subsumed by the sorting time. · **Space:** O(log n) to O(n). The space complexity depends on the implementation of the sorting algorithm. In Java, `Arrays.sort()` for primitive types uses a dual-pivot Quicksort, which requires O(log n) space on average for the recursion stack, but can be O(n) in the worst case.
**Pros:** Much more efficient than the brute-force approach.; Requires minimal extra space if an in-place sorting algorithm is used.
**Cons:** Slower than the optimal hash set approach.; Sorting the array modifies the input array, which might not be desirable in some contexts. A copy would be needed to avoid this, costing extra space.
### Explanation
The main idea here is to leverage sorting to group identical elements together. By sorting the `candyType` array, we ensure that all occurrences of a specific candy type are contiguous. After sorting, we can find the number of unique types by simply iterating through the array and counting how many times the value changes. We initialize a counter for unique types to 1 (to account for the first type). Then, we loop from the second element to the end of the array. In each step, we compare the current candy with the previous one. If `candyType[i]` is different from `candyType[i-1]`, we have found a new unique type and increment our counter. After this single pass, we have the total count of unique candy types. The final answer is the minimum of this count and the number of candies Alice is allowed to eat (`n / 2`).

```java
import java.util.Arrays;

class Solution {
    public int distributeCandies(int[] candyType) {
        int n = candyType.length;
        int maxAllowed = n / 2;

        Arrays.sort(candyType);

        int uniqueCount = 1;
        for (int i = 1; i < n; i++) {
            if (candyType[i] != candyType[i - 1]) {
                uniqueCount++;
            }
        }

        return Math.min(uniqueCount, maxAllowed);
    }
}
```
### Algorithm
- Calculate the maximum number of candies Alice can eat: `maxAllowed = candyType.length / 2`.
- Sort the `candyType` array in non-decreasing order.
- Initialize a counter for unique types, `uniqueCount`, to 1 (since the first element is always a unique type).
- Iterate through the sorted array from the second element (`i = 1` to `n-1`).
- Compare the current element `candyType[i]` with the previous element `candyType[i-1]`.
- If they are different, it signifies a new unique type, so increment `uniqueCount`.
- After the loop, `uniqueCount` holds the total number of distinct candy types.
- Return `Math.min(uniqueCount, maxAllowed)`.

## Using a HashSet
The most efficient approach uses a `HashSet` data structure. A hash set is ideal for this problem because it only stores unique elements and provides, on average, constant time complexity for adding elements. By iterating through the candies and adding them to a set, we can quickly find the number of unique types.
**Time:** O(n). We iterate through the `candyType` array of length `n` once. Adding an element to a `HashSet` takes O(1) time on average. Thus, the total time complexity is linear with respect to the number of candies. · **Space:** O(k), where `k` is the number of unique candy types. In the worst case, all `n` candies are of different types, so the space complexity becomes O(n) to store them in the set.
**Pros:** Optimal time complexity of O(n).; The code is concise and clearly expresses the intent of finding unique items.
**Cons:** Requires extra space to store the hash set, which can be up to O(n) in the worst case where all candies are unique.
### Explanation
This approach leverages the properties of a `HashSet` to efficiently count unique elements. We initialize an empty `HashSet`. Then, we iterate through the `candyType` array. For each candy, we attempt to add it to the set. The `add` operation of a `HashSet` will only succeed if the element is not already present, thus automatically filtering out duplicates. This process takes, on average, O(1) time for each candy. After iterating through all the candies, the `size()` of the `HashSet` gives us the exact number of distinct candy types. As before, the maximum number of different types Alice can eat is limited by the number of candies she is allowed to eat (`n / 2`). Therefore, the answer is the minimum of the number of unique types (the set's size) and `n / 2`.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int distributeCandies(int[] candyType) {
        int n = candyType.length;
        int maxAllowed = n / 2;

        Set<Integer> uniqueTypes = new HashSet<>();
        for (int candy : candyType) {
            uniqueTypes.add(candy);
        }

        return Math.min(uniqueTypes.size(), maxAllowed);
    }
}
```
### Algorithm
- Calculate the maximum number of candies Alice can eat: `maxAllowed = candyType.length / 2`.
- Create an empty `HashSet` to store the types of candies.
- Iterate through each `candy` in the `candyType` array.
- For each `candy`, add it to the `HashSet`. The set will automatically handle duplicates, ensuring only unique types are stored.
- After the loop, the number of unique candy types is simply the size of the `HashSet`.
- Return the minimum of the set's size and `maxAllowed`.

# Solutions
### Java

```java
class Solution {
public
  int distributeCandies(int[] candyType) {
    Set<Integer> s = new HashSet<>();
    for (int c : candyType) {
      s.add(c);
    }
    return Math.min(candyType.length >> 1, s.size());
  }
}

```

### CPP

```cpp
class Solution {
public:
  int distributeCandies(vector<int> &candyType) {
    unordered_set<int> s;
    for (int c : candyType)
      s.insert(c);
    return min(candyType.size() >> 1, s.size());
  }
};

```

### Python

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

```