Min Rounds Complete Tasks LeetCode 2244

LeetCode 2244 — Minimum Rounds to Complete All Tasks — gives you an array of integers where each element represents the difficulty level of a task. In each round you must complete exactly 2 or 3 tasks, and all tasks in a single round must share the same difficulty level. Your goal is to find the minimum number of rounds needed to complete all tasks, or return -1 if it is impossible.

The impossibility condition is immediately clear: if any difficulty level appears exactly once, you cannot group that single task into a round of 2 or 3. Every other configuration has a valid decomposition. The challenge is finding the minimum number of rounds, which requires understanding how to optimally split a frequency count into groups of 2 and 3.

This problem is rated Medium and is a clean example of a greedy counting pattern: you do not need dynamic programming or backtracking. Once you understand the mathematical relationship between a frequency and the minimum number of groups, the entire solution collapses into a one-pass frequency count followed by a simple formula per level.

The first key observation is about impossibility: if a difficulty level appears exactly once (frequency = 1), there is no valid round for it — a round requires 2 or 3 tasks. So frequency 1 immediately returns -1. Every other frequency has at least one valid decomposition.

The second observation is about small frequencies: frequency 2 needs exactly one round of 2; frequency 3 needs exactly one round of 3. What about frequency 4? Two rounds of 2 (not one round of 4, since rounds are capped at 3). Frequency 5? One round of 2 plus one round of 3. Frequency 6? Two rounds of 3. The pattern emerges — any integer >= 2 can be expressed as a non-negative integer combination of 2s and 3s.

This mathematical fact — that every integer >= 2 is representable as a sum of 2s and 3s — is the engine of the entire solution. It means the only impossible case is frequency = 1, and for every other frequency we just need to compute the minimum number of groups.

To minimize rounds, prefer groups of 3 over groups of 2 — a group of 3 completes more tasks per round. So greedily take as many 3s as possible and handle the remainder with 2s. For a frequency c, divide by 3 and check the remainder.

When the remainder is 0 (c % 3 == 0), all groups are size 3: rounds = c / 3. When the remainder is 2 (c % 3 == 2), take c / 3 rounds of 3 plus one round of 2: rounds = c / 3 + 1. When the remainder is 1 (c % 3 == 1), we cannot use a single task in isolation — instead, replace one group of 3 with two groups of 2: rounds = (c - 4) / 3 + 2, which simplifies to c / 3 + 1.

Notice that both the remainder-1 and remainder-2 cases give c / 3 + 1 (using integer division). This is not a coincidence — it is exactly the definition of ceiling division by 3.

The three-case analysis collapses to a single expression: rounds = ceil(c / 3) for any c >= 2. In integer arithmetic this is (c + 2) // 3 in Python or (c + 2) / 3 in Java. This single formula handles all valid frequencies without branching.

Why does ceiling division by 3 work? When c is divisible by 3, ceil(c/3) = c/3. When c % 3 == 1 or c % 3 == 2, ceil(c/3) = c/3 + 1. In both non-zero-remainder cases, we need one extra partial group — exactly what floor(c/3) + 1 gives. Ceiling division captures this uniformly.

The complete algorithm: count frequencies using a hash map, check if any frequency equals 1 (return -1), then sum ceil(freq/3) across all unique difficulty levels. Time complexity is O(n) for the frequency count; space complexity is O(n) for the hash map in the worst case where all tasks have distinct difficulty levels.

Consider tasks = [2, 2, 3, 3, 2, 4, 4, 4, 4, 4]. First compute frequencies: difficulty 2 appears 3 times, difficulty 3 appears 2 times, difficulty 4 appears 5 times. No frequency is 1, so -1 is not returned.

Apply ceil(freq/3) to each level: ceil(3/3) = 1 round for difficulty 2 (one group of 3), ceil(2/3) = 1 round for difficulty 3 (one group of 2), ceil(5/3) = 2 rounds for difficulty 4 (one group of 3 plus one group of 2). Total = 1 + 1 + 2 = 4 rounds.

We can verify the difficulty-4 decomposition: 5 tasks split as 3 + 2 — two rounds, both valid. The greedy formula correctly identifies that the remainder-2 case needs one extra partial round.

Python solution uses Counter from collections for frequency counting, then a generator expression over the counts. The impossibility check and the ceil formula are both one-liners: if any(c == 1 for c in counts.values()): return -1, then return sum((c + 2) // 3 for c in counts.values()). Total: about 5 lines of code. Java uses a HashMap<Integer, Integer> for frequency counting, then iterates the values with the same (count + 2) / 3 formula.

Both implementations run in O(n) time and O(n) space. The space comes from the frequency map, which in the worst case stores one entry per unique difficulty level. If all n tasks have distinct difficulties, all frequencies are 1 and the function immediately returns -1 — so the extreme-space case is also caught early.

A common pitfall is using floating-point division: math.ceil(count / 3) introduces risk of floating-point imprecision for very large counts (e.g., count near 10^9). The integer formula (count + 2) // 3 is always exact and is the recommended approach.

Minimum Rounds to Complete All Tasks belongs to the greedy counting family — problems where the optimal answer per independent group can be computed analytically rather than by search. Task Scheduler (LeetCode 621) is the closest relative: it also groups tasks by frequency and asks for the minimum time to execute all tasks given a cooldown constraint, requiring similar frequency-first thinking.

Minimum Deletions to Make Character Frequencies Unique (LeetCode 1647) applies the same pattern in the opposite direction: instead of decomposing frequencies into groups, you reduce frequencies so no two levels share a count. Top K Frequent Elements (LeetCode 347) is the frequency-counting prerequisite — mastering bucket sort and heap-based frequency retrieval prepares you for the greedy counting family.

More broadly, any problem asking for minimum rounds, minimum operations, or minimum deletions over independently grouped items is a candidate for this approach: count the groups, apply a per-group formula greedily, sum the results. Recognizing this template means you can solve novel variants quickly by focusing on the per-group formula rather than the overall search structure.