LeetCode 2244 - Minimum Rounds to Complete All Tasks

LeetCode Problem 2244

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Greedy, Counting

Solution

Here is a complete, detailed technical solution guide for LeetCode 2244 - Minimum Rounds to Complete All Tasks following your formatting and content requirements.

Problem Understanding

The problem provides a 0-indexed array tasks, where each element represents a task's difficulty level. Each round, you are allowed to complete exactly 2 or 3 tasks of the same difficulty. The goal is to determine the minimum number of rounds required to complete all tasks, or return -1 if completing them under these constraints is impossible.

In other words, for every difficulty level, we must group the tasks into sets of size 2 or 3. If a difficulty has only 1 task, it is impossible to complete, so the output is -1. If a difficulty has multiple tasks, the optimal strategy is to combine them into as many sets of 3 as possible because larger groups reduce the number of rounds, and then handle the remainder using sets of 2 if necessary.

Input details: 1 <= tasks.length <= 10^5 and 1 <= tasks[i] <= 10^9. This indicates that the input can be very large, so a solution must operate in linear or near-linear time. Also, the difficulty values themselves can be very large but do not need sorting, only counting.

Edge cases to consider: difficulties that appear only once, difficulties with exactly two tasks, and difficulties that leave a remainder of 1 when divided by 3 (requiring adjustment to avoid impossible grouping).

Approaches

Brute Force

A naive approach would attempt all possible combinations of 2- and 3-task groupings for each difficulty using recursion or backtracking. While this guarantees correctness, it is extremely inefficient due to exponential time complexity. With n up to 10^5, this approach is infeasible.

Optimal Approach

The key observation is that for each difficulty, the number of rounds can be computed greedily:

• If count % 3 == 0, all tasks can be grouped in sets of 3.
• If count % 3 == 1, one 3-group is converted into two 2-groups (since 3 + 1 = 4 → two 2-groups).
• If count % 3 == 2, one extra 2-group is added.

This ensures the minimum number of rounds because sets of 3 are preferred to minimize rounds, and remainders are handled with sets of 2. If the count is 1, it is impossible.

We can efficiently implement this by counting the frequency of each difficulty using a hash map, then applying the above rules for each difficulty.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Try all possible groupings; infeasible
Optimal	O(n)	O(n)	Count frequencies and compute minimum rounds using modulo arithmetic

Algorithm Walkthrough

1. Initialize a hash map (or dictionary) freq to count the frequency of each difficulty level.
2. Iterate over the tasks array, incrementing the count of each difficulty in freq.
3. Initialize rounds = 0 to keep track of the total rounds.
4. For each difficulty and its count:

• If count == 1, return -1 immediately because it cannot be grouped.

• Otherwise, compute rounds:

• rounds += count // 3 for full 3-task groups.

• If count % 3 != 0, add 1 more round to handle the remainder (either a single 2-task or two 2-task groups).

5. Return the total rounds.

Why it works: Each difficulty is treated independently. Greedy grouping by 3 ensures the minimum number of rounds. Handling the remainder using sets of 2 ensures feasibility without increasing rounds unnecessarily. This guarantees the minimum rounds required for all tasks.

Python Solution

from typing import List
from collections import Counter

class Solution:
    def minimumRounds(self, tasks: List[int]) -> int:
        freq = Counter(tasks)
        rounds = 0
        
        for count in freq.values():
            if count == 1:
                return -1
            rounds += count // 3
            if count % 3 != 0:
                rounds += 1
        
        return rounds

Implementation Explanation:

We use Counter to efficiently count each difficulty. For each difficulty, if its frequency is 1, it is impossible to group, so we return -1. Otherwise, we calculate the number of rounds using integer division and modulo, adding extra rounds when the remainder is 1 or 2. The logic directly follows the algorithm walkthrough.

Go Solution

func minimumRounds(tasks []int) int {
    freq := make(map[int]int)
    for _, t := range tasks {
        freq[t]++
    }
    
    rounds := 0
    for _, count := range freq {
        if count == 1 {
            return -1
        }
        rounds += count / 3
        if count % 3 != 0 {
            rounds++
        }
    }
    
    return rounds
}

Go Notes:

We use a map[int]int to count frequencies. The logic mirrors Python: divide by 3, add an extra round if there is a remainder. Go handles integer division naturally, and the map iteration is straightforward. There are no nil vs empty issues since maps are initialized.

Worked Examples

Example 1: tasks = [2,2,3,3,2,4,4,4,4,4]

Difficulty	Count	Rounds Calculation	Rounds Added
2	3	3 // 3 = 1	1
3	2	2 // 3 = 0, remainder 2 → +1	1
4	5	5 // 3 = 1, remainder 2 → +1	2

Total rounds = 1 + 1 + 2 = 4

Example 2: tasks = [2,3,3]

Difficulty	Count	Action
2	1	Cannot group → return -1
3	2	Would be 1 round if feasible

Output = -1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We iterate once over tasks to count frequencies, and once over freq to compute rounds
Space	O(n)	We store counts of each difficulty in a hash map, at most n entries in worst case

The solution scales linearly with input size, making it efficient for up to 10^5 tasks.

Test Cases

# Provided examples
assert Solution().minimumRounds([2,2,3,3,2,4,4,4,4,4]) == 4  # multiple difficulties
assert Solution().minimumRounds([2,3,3]) == -1               # impossible due to single task

# Edge case: single difficulty, 1 task
assert Solution().minimumRounds([7]) == -1                   # impossible

# Edge case: single difficulty, exactly 2 tasks
assert Solution().minimumRounds([5,5]) == 1                 # exactly 1 round

# Edge case: single difficulty, exactly 3 tasks
assert Solution().minimumRounds([5,5,5]) == 1               # exactly 1 round

# Multiple difficulties, mix of 2s and 3s
assert Solution().minimumRounds([1,1,1,2,2,3,3,3,3]) == 5    # 1->1 round, 2->1 round, 3->2 rounds

# Large input
tasks = [1]*100000
assert Solution().minimumRounds(tasks) == 33334             # 100000 // 3 = 33333 + 1 extra round for remainder

Test	Why
[2,2,3,3,2,4,4,4,4,4]	Validates multiple difficulties and remainder handling
[2,3,3]	Checks impossible case due to single task
[7]	Minimal single-element array, impossible
[5,5]	Minimal 2-element array, feasible
[5,5,5]	Minimal 3-element array, feasible
[1,1,1,2,2,3,3,3,3]	Multiple difficulties with mix of group sizes
[1]*100000	Stress test for large input

Edge Cases

1. Single task of any difficulty: This is impossible to group and must return -1. Our solution directly checks count == 1.
2. Exact multiples of 3: If a difficulty count is divisible by 3, the remainder is zero and no extra rounds are added. This is the optimal scenario, handled naturally by integer division.
3. Remainder 1 scenario: For counts like 4, 7, 10, etc., the greedy division by 3 leaves a remainder of 1. Our algorithm adds an extra round for the leftover 1 by converting one 3-group into two