Distribute Candies solution and explanation
Google
9 more videos on this problem
Distribute Candies | Live Coding with Explanation | Leetcode - 575Algorithms Made Easy · 3:20 · 5K views
575. Distribute Candies | EASY PROBLEM | LEETCODE | CODE EXPLAINERcode Explainer · 5:39 · 3K views
Distribute Candies | LeetCode 575 | Hash TableNaresh Gupta · 4:07 · 1K views
Leetcode - Distribute Candies (Python)Timothy H Chang · 2:28 · 1K views
Distribute Candies | Leetcode 575Coding Decoded · 8:05 · 448 views
DistributeCandies575LeetCode - Solution to LeetCode 575 - Distribute candiesLEETCODE MASTER · 6:27 · 393 views
Daily Leetcode #335: Mar 01, 2021 - 575. Distribute CandiesProgramming Live with Larry · 8:29 · 286 views
Distribute Candies | LeetCode 575 | Coders CampCoders Camp · 5:31 · 263 views
How to Solve "575 Distribute Candies" on LeetCode? - JavascriptBecoming A Better Dev (with David) · 3:41 · 204 views
Leetcode Problem 575: Distribute Candies | Algorithm ExplainedMohit Chhabra · 15:14 · 166 views
The 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.length2 <= n <= 104nis 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.
def distributeCandies(candyType):
return min(len(set(candyType)), len(candyType) // 2)import java.util.HashSet;
public class Solution {
public int distributeCandies(int[] candyType) {
HashSet<Integer> uniqueCandies = new HashSet<>();
for (int candy : candyType) {
uniqueCandies.add(candy);
}
return Math.min(uniqueCandies.size(), candyType.length / 2);
}
}#include <unordered_set>
#include <vector>
using namespace std;
class Solution {
public:
int distributeCandies(vector<int>& candyType) {
unordered_set<int> uniqueCandies(candyType.begin(), candyType.end());
return min(uniqueCandies.size(), candyType.size() / 2);
}
};function distributeCandies(candyType) {
const uniqueCandies = new Set(candyType);
return Math.min(uniqueCandies.size, candyType.length / 2);
}#include <stdio.h>
#include <stdlib.h>
int cmpfunc(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
int distributeCandies(int* candyType, int candyTypeSize) {
qsort(candyType, candyTypeSize, sizeof(int), cmpfunc);
int uniqueTypes = 1;
for (int i = 1; i < candyTypeSize; i++) {
if (candyType[i] != candyType[i - 1])
uniqueTypes++;
}
return (uniqueTypes < candyTypeSize / 2) ? uniqueTypes : candyTypeSize / 2;
}using System;
using System.Collections.Generic;
public class Solution {
public int DistributeCandies(int[] candyType) {
HashSet<int> uniqueCandies = new HashSet<int>(candyType);
return Math.Min(uniqueCandies.Count, candyType.Length / 2);
}
}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.
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: 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.
from collections import Counter
def distributeCandies(candyType):
count = Counter(candyType)
uniqueTypes = len(count)
return min(uniqueTypes, len(candyType) // 2)import java.util.HashMap;
public class Solution {
public int distributeCandies(int[] candyType) {
HashMap<Integer, Integer> candyMap = new HashMap<>();
for (int candy : candyType) {
candyMap.put(candy, candyMap.getOrDefault(candy, 0) + 1);
}
return Math.min(candyMap.size(), candyType.length / 2);
}
}#include <unordered_map>
#include <vector>
using namespace std;
class Solution {
public:
int distributeCandies(vector<int>& candyType) {
unordered_map<int, int> candyMap;
for (int candy : candyType) {
candyMap[candy]++;
}
return min(candyMap.size(), candyType.size() / 2);
}
};function distributeCandies(candyType) {
const candyMap = {};
candyType.forEach(candy => {
candyMap[candy] = (candyMap[candy] || 0) + 1;
});
return Math.min(Object.keys(candyMap).length, candyType.length / 2);
}#include <stdio.h>
#include <stdlib.h>
int distributeCandies(int* candyType, int candyTypeSize) {
int maxTypes = candyTypeSize / 2;
int *hash = (int*)calloc(200001, sizeof(int));
int uniqueCount = 0;
for (int i = 0; i < candyTypeSize; i++) {
int index = candyType[i] + 100000;
if (hash[index] == 0) {
uniqueCount++;
}
hash[index]++;
}
free(hash);
return uniqueCount < maxTypes ? uniqueCount : maxTypes;
}using System;
using System.Collections.Generic;
public class Solution {
public int DistributeCandies(int[] candyType) {
Dictionary<int, int> candyMap = new Dictionary<int, int>();
foreach (var candy in candyType) {
if (!candyMap.ContainsKey(candy)) {
candyMap[candy] = 0;
}
candyMap[candy]++;
}
return Math.Min(candyMap.Count, candyType.Length / 2);
}
}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.
Time Complexity: O(n) for creating the counter.
Space Complexity: O(n) for storing unique types in the counter.
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.
function distributeCandies(candyType: number[]): number {
const s = new Set(candyType);
return Math.min(s.size, candyType.length >> 1);
}func distributeCandies(candyType []int) int {
s := hashset.New()
for _, c := range candyType {
s.Add(c)
}
return min(len(candyType)>>1, s.Size())
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Using Sets for Unique Types | Time Complexity: O(n) because we iterate over the array to create the set. |
| Approach 2: Frequency Map and Counting | Time Complexity: O(n) for creating the counter. |
| Hash Table | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Using Set for Unique Types | O(n) | O(n) | Best general solution. Quickly counts unique candy types with minimal code. |
| Frequency Map and Counting | O(n) | O(n) | Useful when you also need counts of each candy type or when extending the problem. |
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.