Abstract / Summary

Given a number of candies and children, find the minimum number each child must get so all candies are distributed evenly or with at most one extra.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 71% (500k+ submissions).

Typical patterns to solve this problem:

• Array
• Hash Table

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the problem of determining the maximum number of different candy types a person can receive when the total number of candies is split equally between two people. The method receives a list of integers representing candy types, builds a collection of unique types, and then computes the answer using a simple arithmetic rule.

Key Steps

The algorithm proceeds through three distinct phases.

The first phase creates an empty set named have. This set is used to store distinct candy types encountered while iterating over the input list.

have = set()

The second phase iterates over each element i in candyType and inserts it into the set. Because a set automatically discards duplicate entries, the resulting collection contains exactly one instance of each candy type present in the original list.

for i in candyType:
    have.add(i)

The third phase calculates two values. variety is assigned the length of the original list, representing the total number of candies. The expression len(have) yields the count of unique candy types. The final result is the smaller of half the total candy count (integer division) and the number of unique types, which matches the problem’s constraint that a person can receive at most half of the candies.

variety = len(candyType)
return min(variety // 2, len(have))

Edge Cases

The code naturally handles several edge conditions without additional checks.

When the input list is empty, the set remains empty, variety becomes zero, and the min function returns zero, correctly indicating that no candies can be distributed.

If all candies are of the same type, the set will contain a single element. The min operation will then compare half the total count with one, yielding one as the maximum distinct types the person can receive, which aligns with the rule that each type can be taken at most once.

When the number of unique types exceeds half the total number of candies, the integer division variety // 2 limits the result, ensuring the person never receives more candies than are available for their share.

The use of integer division automatically truncates any fractional half, so odd-length lists are handled correctly by rounding down to the nearest whole number of candies that can be given to one person.

Performance Optimizations

The implementation leverages the intrinsic properties of Python’s built-in set type to achieve efficient duplicate elimination. Adding each element to a set runs in amortized constant time, allowing the entire deduplication process to scale linearly with the size of the input list.

By computing the length of the original list once and reusing it, the code avoids repeated traversal of the input data. The final min call operates on two scalar values, incurring negligible overhead.

Overall, the solution maintains a tight loop with minimal auxiliary operations, resulting in a fast execution path even for large input arrays. The reliance on native data structures ensures that the underlying C-level implementations handle memory allocation and hashing efficiently, contributing to the method’s high performance.

Imagine you have a big bag filled with many different kinds of colorful candies. Some candies look the same and others look different. The goal is to share these treats fairly.

First, a special empty tray is prepared to keep track of how many unique types of candy are in the bag. Every single piece of candy is picked up one by one. If a candy is a new kind that hasn't been seen before, it gets placed on the tray. If a matching candy has already been spotted, it gets set aside because there is already enough of that kind on the tray.

After looking at every candy in the bag, the number of candies on the tray shows all the different flavors available. There is also a rule that only half of the total candies from the bag can be chosen. The solution looks at how many unique types are sitting on the tray and compares that to the limit of how many candies are allowed to be taken. If there are fewer unique types of candy than the limit, then every single different type can be enjoyed. If there are more unique types than the limit, then only the amount allowed by the limit can be picked, ensuring a good variety without taking too many.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Java		Python					TS
	WalkCCC	C++	Java		Python
	leetcode.ca	C++	Java		Python		Go			TS
	LeetcodeHelp	C++	Java		Python
	Progiez	C++	Java		Python
github	BigEggStudy			C#
	black-shadows	C++
	charles-wangkai		Java
	DimitrisJim								C
	everthis					JS
	fpdjsns	C++
	gouthampradhan		Java
	halfrost						Go
	JoshCrozier					JS
	Krazune	C++
	linouk23	C++
	lkwq007				Python
	muhammadfarhankt						Go
	ruoru							Rust
	shreymehul			C#
	suxrobGM			C#
	varunu28		Java
	YuriSpiridonov				Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
DimitrisJim	C
everthis	JavaScript
fpdjsns	C++
gouthampradhan	Java
halfrost	Go
JoshCrozier	JavaScript
Krazune	C++
linouk23	C++
lkwq007	Python
muhammadfarhankt	Go
ruoru	Rust
shreymehul	C#
suxrobGM	C#
varunu28	Java
YuriSpiridonov	Python
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality