Abstract / Summary

You must finish all tasks in rounds where each round can handle at most two tasks of the same type. Find the fewest rounds needed.

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 63% (200k+ submissions).

Typical patterns to solve this problem:

• Array
• Counting
• Greedy
• 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 minimum number of rounds required to complete a set of tasks, where each round can process either two or three tasks of the same type. The algorithm proceeds in three logical phases: counting the occurrences of each distinct task, evaluating the feasibility of completing each task type, and aggregating the minimal round count using a mathematical shortcut.

Counting Frequencies

The first phase builds a frequency map that records how many times each task identifier appears in the input list. By employing a defaultdict initialized to zero, the code avoids explicit existence checks while iterating over the tasks.

freq = defaultdict(int)
for t in tasks:
    freq[t] += 1

This construct ensures that each distinct task value becomes a key in freq with its corresponding count as the value.

Determining Rounds

The second phase iterates over the keys of the frequency map. For each task type, the algorithm checks whether the count equals one, which would make it impossible to form a valid round (since a round must contain at least two tasks). In that case, the function returns -1 immediately, signaling infeasibility.

If the count is greater than one, the code computes the minimal number of rounds by dividing the count by three and rounding up. The ceil function captures the optimal combination of two-task and three-task rounds without enumerating all possibilities. The result for each task type is accumulated into a running total.

result = 0
for f in freq:
    if freq[f] == 1:
        return -1
    result += ceil(freq[f] / 3)

The comment block preceding this logic enumerates example decompositions for counts from one through nine, illustrating how the ceiling division aligns with the optimal mix of two- and three-task rounds.

Edge Cases

The algorithm explicitly handles the scenario where a task type appears exactly once. Since a single task cannot be grouped into a round of size two or three, the function returns -1 to indicate that the overall task list cannot be completed under the given constraints. This early exit prevents unnecessary computation for the remaining task types.

Another implicit edge case is the handling of large counts. By using the mathematical ceiling of the division by three, the code correctly accounts for any remainder that would otherwise require an additional round of two tasks. For example, a count of five yields ceil(5/3) = 2, which corresponds to one round of three tasks and one round of two tasks.

Performance Considerations

The solution achieves linear time performance relative to the length of the input list by performing a single pass to construct the frequency map and a second pass over the distinct task identifiers. The use of defaultdict eliminates conditional branching during counting, contributing to a streamlined iteration.

The aggregation step leverages the ceil function from the math library, which provides a constant-time calculation for each frequency value. This avoids the need for iterative subtraction or explicit case analysis for each possible remainder, thereby reducing overhead.

Overall, the code demonstrates a concise and efficient approach to the problem, combining built-in data structures with a mathematical insight to minimize both computational steps and code complexity.

Imagine a big basket full of colored blocks where each number represents a different color. The goal is to group these blocks so that every group has either two or three blocks of the same color, because those are the only amounts that fit in our mystery boxes.

First, the code goes through the basket and makes little piles of each color so it can see exactly how many blocks of each kind are inside. It counts them up and keeps track of the totals.

Next, it looks at each color one by one to see how to pack them. If there is only one block of a color, the mission is impossible because the rules say groups must have at least two blocks, so it stop right there.

For all the other colors, the computer figures out how to scoop them up using the biggest handfuls possible. By taking groups of three as often as it can, it calculates the smallest number of rounds needed to empty the basket. It keeps adding up the number of rounds until every single block has been put away.

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	Rust	TS
	Progiez	C++	Java	Python
github	black-shadows	C++
	charles-wangkai		Java
	everthis				JS
	fpdjsns	C++
	fsq	C++
	JoshCrozier				JS
	lkwq007			Python
	martianoff					Scala
	shreymehul							C#
	trung-hn			Python
	varunu28		Java
	vthwang		Java
	yuanliu666						Kotlin
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fpdjsns	C++
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
martianoff	Scala
shreymehul	C#
trung-hn	Python
varunu28	Java
vthwang	Java
yuanliu666	Kotlin

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