Skip to main content

575 - Distribute Candies

Difficulty: Easy | Pattern: HashSet | Company tags: Amazon, Google

Problem Statement​

Alice has n candies, where the i-th candy is of type candyType[i]. Alice noticed she started to gain weight, so she visited a doctor.

The doctor advised Alice to eat only 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  (eat one of each type)

Example 2:

Input: candyType = [1,1,2,3]
Output: 2  (can only eat 2 out of 4)

Example 3:

Input: candyType = [6,6,6,6]
Output: 1  (all same type)

Solution​

Key insight: Alice can eat n//2 candies. She wants maximum variety. The answer is min(distinct_types, n//2).

def distributeCandies(candyType: list[int]) -> int:
    return min(len(set(candyType)), len(candyType) // 2)

Algorithm Flow​

Dry Run​

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

  • distinct types = 3 (set {1,2,3})
  • n//2 = 3
  • min(3, 3) = 3 ✓

candyType = [6,6,6,6]

  • distinct = 1
  • n//2 = 2
  • min(1, 2) = 1 ✓

Edge Cases​

  • All same type → 1
  • All different → n//2 (limited by quota, not variety)
  • Exactly n//2 distinct types → n//2

Complexity​

  • Time: O(n)
  • Space: O(n) for the set

Key Terms​

TermDefinition
Hash setA data structure storing unique elements with O(1) average lookup/insert, used here to count distinct candy types.
Distinct countThe number of unique values in an array — len(set(arr)) — the ceiling on achievable variety.
Quota / eating limitThe fixed number of items Alice is allowed to eat (n // 2), independent of how many types exist.
Greedy min-based boundA pattern where the answer is min(A, B) because two independent constraints (variety available vs. quota allowed) each cap the result.
Bounding constraintWhichever of the two limits (distinct types or quota) is smaller; it determines the final answer.

FAQ​

Q1: Why does min(len(set(candyType)), n // 2) give the correct answer? Because Alice is capped by two independent limits: how many different types exist, and how many candies she's allowed to eat. She can never exceed either, so the achievable maximum is the smaller of the two.

Q2: Why use a hash set instead of sorting the array? A hash set gives O(n) time to find distinct types, versus O(n log n) for sorting. Since we only need the count of unique values (not their order), sorting adds no benefit and costs more time.

Q3: What happens if all candies are of the same type? The set has size 1, n // 2 is some larger number, so min(1, n//2) = 1 — Alice can only ever taste one type, no matter how many candies she has.

Q4: Can this be solved without extra space? Not in O(n) time for an unsorted array — you need either a hash set (O(n) space) or an in-place sort (O(1) extra space but O(n log n) time). The hash set is the standard trade-off for this problem.

Q5: How does this generalize to the "reduce array size by half" style problems? The same greedy min-based idea extends to problems like 1338 - Reduce Array Size to the Half, where you again compare "how many distinct/frequent groups exist" against "how many removals/picks are allowed," and greedily satisfy the tighter constraint first.

Quick Revision​

  • Problem: maximize distinct candy types Alice eats, but she can only eat n / 2 candies total.
  • Two independent caps: distinct_types (variety available) and n // 2 (quota allowed).
  • Answer is always min(distinct_types, n // 2) — no simulation or DP needed.
  • Use a hash set to compute distinct_types in O(n) time.
  • If distinct_types <= n // 2, Alice eats one of every type and still has quota left over.
  • If distinct_types > n // 2, she's quota-limited and eats n // 2 different types.
  • Time complexity: O(n) to build the set; Space complexity: O(n) worst case (all unique).
  • Edge cases: all-same-type array (answer = 1), all-unique array (answer = n // 2).
  • Core interview signal: recognize "min of two independent bounds" as a standalone pattern, not just this problem.
  • 1338 - Reduce Array Size to the Half — greedy selection bounded by a count/quota trade-off, uses frequency counting instead of a plain set.
  • Contains Duplicate / Intersection of Two Arrays style problems — same hash-set-for-uniqueness pattern, not yet present as separate files in this directory.