Skip to main content
Talentd

Distribute Candies - Solution & Explanation

EasyArrayHash Table13 min readAsked at: Google, Bloomberg, Liveramp
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You receive an array where each value represents a candy type. Alice must eat exactly n/2 candies from the array. The goal is to maximize the number of different types she eats. The key observation: Alice cannot eat more than n/2 candies, but she also cannot exceed the total number of unique candy types available.

This problem sits at the intersection of Array traversal and counting unique elements using a Hash Table. Once you recognize the constraint n/2, the solution becomes a simple comparison between the number of unique candy types and the maximum candies Alice can eat.

Approach 1: Using Sets for Unique Types (O(n) time, O(n) space)

Insert every candy type into a set. A set automatically removes duplicates, leaving only the unique candy types. Let uniqueTypes be the size of this set and limit = n / 2. Alice can eat at most limit candies, so the maximum distinct types she can eat is min(uniqueTypes, limit). The algorithm iterates once through the array to build the set and then returns this minimum value. This approach is clean and relies on constant-time hash insertions.

This is usually the first solution engineers write during interviews because it maps directly to the problem statement: count unique values and compare them with the allowed number of candies.

Approach 2: Frequency Map and Counting (O(n) time, O(n) space)

Instead of a set, build a frequency map using a hash table. Iterate through the array and increment the count for each candy type. The number of keys in the map represents the number of unique candy types. Once the map is built, compute limit = n / 2 and return min(number_of_keys, limit). The frequency values themselves are not strictly required for this problem, but constructing the map demonstrates how duplicate tracking works in many counting problems.

This approach is slightly more verbose than the set solution but useful if you later extend the problem to require counts or additional constraints.

Recommended for interviews: The set-based solution is the expected answer. It shows you immediately recognize the constraint that Alice can eat only n/2 candies and that the problem reduces to counting unique types. Interviewers usually want to see the reasoning: maxDistinct = min(uniqueTypes, n/2). Mentioning the frequency map alternative also demonstrates familiarity with common hash table counting patterns.

Approach 1: Approach 1: Using Sets for Unique Types

The goal is to find the maximum number of unique types of candies Alice can eat. We can take the following steps:

  • Use a set to find the unique types of candies. The set will store each unique candy type encountered.
  • Calculate the number of candies Alice can eat: maxCandies = n / 2.
  • The result is the minimum of the number of unique candy types and maxCandies.

This solution creates a set from the list of candies to determine how many unique types there are. The minimum of the number of unique types and n / 2 candies Alice can eat is the answer.

Code

PythonCJavaC++C#JavaScript

Python

C

Java

C++

C#

JavaScript

Complexity

Time Complexity: O(n) because we iterate over the array to create the set.
Space Complexity: O(n) for storing the unique types in a set.

Try this approach in the editor →

Approach 2: Approach 2: Frequency Map and Counting

For another perspective:

  • Use a frequency map to count occurrences of each candy type.
  • Count how many distinct candy types exist.
  • Return the minimum between the number of distinct types and n / 2.
This approach relies on counting mechanisms to determine the maximum distinct types she can consume within limits.

This python solution uses Counter to determine frequency counts, which inherently provides unique element counts. The minimal value between this count and n / 2 determines how many types Alice can eat.

Code

PythonCJavaC++C#JavaScript

Python

C

Java

C++

C#

JavaScript

Complexity

Time Complexity: O(n) for creating the counter.
Space Complexity: O(n) for storing unique types in the counter.

Try this approach in the editor →

Approach 3: 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.

The time complexity is O(n), and the space complexity is O(n). Where n is the number of candies.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Using Sets for Unique Types

Time Complexity: O(n) because we iterate over the array to create the set.
Space Complexity: O(n) for storing the unique types in a set.

Approach 2: Frequency Map and Counting

Time Complexity: O(n) for creating the counter.
Space Complexity: O(n) for storing unique types in the counter.

Hash Table—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Using Set for Unique TypesO(n)O(n)Best general solution. Quickly counts unique candy types with minimal code.
Frequency Map and CountingO(n)O(n)Useful when you also need counts of each candy type or when extending the problem.

Video Solution

Distribute Candies | Live Coding with Explanation | Leetcode - 575 • Algorithms Made Easy • 5,103 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Distribute Candies easy or hard?
Distribute Candies is classified as an Easy problem. The challenge is recognizing that the answer depends only on the number of unique candy types and the constraint that Alice can eat at most n/2 candies.
Distribute Candies Python/Java solution
In Python, use set(candyType) to compute the number of unique values and return min(len(set(candyType)), len(candyType)//2). In Java, use a HashSet to store candy types and return Math.min(set.size(), candyType.length/2). Both implementations run in O(n) time.
How to solve Distribute Candies in O(n)?
Iterate through the array and store each candy type in a hash set. The set size represents the number of unique candy types. Compute n/2 (the maximum candies Alice can eat) and return min(uniqueTypes, n/2). This guarantees the maximum distinct types in linear time.
What is the best approach for Distribute Candies?
The optimal approach uses a hash set to count unique candy types. Insert all values into a set and compute min(uniqueTypes, n/2). This runs in O(n) time with O(n) space and directly captures the constraint that Alice can only eat half of the candies.
Is Distribute Candies asked at Google/Amazon/Meta?
Distribute Candies is a common easy-level interview problem used by companies like Amazon and Meta to test understanding of sets, hash tables, and basic counting logic. It often appears in early interview rounds or coding screens.
What data structure is used in Distribute Candies?
The most common data structure is a hash set, which stores unique candy types and eliminates duplicates automatically. A hash map (frequency map) is another valid option if you want to track counts of each candy type.
What is the time complexity of Distribute Candies?
The optimal solution runs in O(n) time because the array is scanned once to determine unique candy types. Hash set insertions are O(1) on average. Space complexity is O(n) in the worst case if all candies are different.

Ready to solve this problem?

Practice Distribute Candies with our built-in code editor and test cases.

Practice on FleetCode
Previous

Check if Grid Satisfies Conditions

Next

Minimum Number of Operations to Satisfy Conditions