Watch 10 video solutions for Minimum Rounds to Complete All Tasks, a medium level problem involving Array, Hash Table, Greedy. This walkthrough by codestorywithMIK has 7,032 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a 0-indexed integer array tasks, where tasks[i] represents the difficulty level of a task. In each round, you can complete either 2 or 3 tasks of the same difficulty level.
Return the minimum rounds required to complete all the tasks, or -1 if it is not possible to complete all the tasks.
Example 1:
Input: tasks = [2,2,3,3,2,4,4,4,4,4] Output: 4 Explanation: To complete all the tasks, a possible plan is: - In the first round, you complete 3 tasks of difficulty level 2. - In the second round, you complete 2 tasks of difficulty level 3. - In the third round, you complete 3 tasks of difficulty level 4. - In the fourth round, you complete 2 tasks of difficulty level 4. It can be shown that all the tasks cannot be completed in fewer than 4 rounds, so the answer is 4.
Example 2:
Input: tasks = [2,3,3] Output: -1 Explanation: There is only 1 task of difficulty level 2, but in each round, you can only complete either 2 or 3 tasks of the same difficulty level. Hence, you cannot complete all the tasks, and the answer is -1.
Constraints:
1 <= tasks.length <= 1051 <= tasks[i] <= 109
Note: This question is the same as 2870: Minimum Number of Operations to Make Array Empty.
Problem Overview: You receive an array where each value represents the difficulty of a task. In one round you can complete either 2 or 3 tasks of the same difficulty. The goal is to determine the minimum number of rounds required to complete all tasks. If any task difficulty appears only once, finishing all tasks becomes impossible.
The key observation: tasks are independent across difficulty levels. You never mix different difficulties in the same round, so the problem reduces to computing the minimum number of rounds needed for each frequency count.
Approach 1: Divide and Conquer with Frequency Breakdown (O(n) time, O(n) space)
Start by counting occurrences of each difficulty using a hash map from the hash table toolkit. Each frequency becomes a smaller subproblem: how many rounds are needed to finish f identical tasks when each round can remove either 2 or 3 tasks. You recursively reduce the count by prioritizing groups of 3 because they minimize the total rounds. When a remainder of 1 appears (for example f = 4 or f = 7), convert one group of 3 into two groups of 2. If a frequency equals 1, the recursion fails because neither 2 nor 3 tasks can be formed.
This approach conceptually divides the problem by difficulty value and solves each group independently. The array scan and hash counting cost O(n) time, and the map stores at most n unique difficulties, so space complexity is O(n). It clearly illustrates why grouping by three tasks produces the fewest rounds.
Approach 2: Dynamic Programming on Task Frequency (O(n) time, O(n) space)
Another way to think about the problem is as a small dynamic programming recurrence. For a given frequency f, define dp[i] as the minimum rounds needed to finish i tasks. The recurrence becomes dp[i] = 1 + min(dp[i-2], dp[i-3]) because each round removes either 2 or 3 tasks. Precompute values up to the maximum frequency found in the array. If a state becomes unreachable (like i = 1), the difficulty cannot be completed.
Before applying DP, compute frequencies using an array traversal and counting step. Then evaluate the recurrence for each frequency and accumulate the result. The DP table grows only up to the largest frequency, so the total work remains linear relative to the number of tasks.
Recommended for interviews: Interviewers expect the counting + greedy reasoning approach. After building the frequency map, compute rounds using the formula ceil(freq / 3) while handling the freq == 1 edge case. This runs in O(n) time with O(n) space and demonstrates strong intuition about greedy grouping. Explaining the DP formulation still helps show deeper understanding of the underlying recurrence.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Divide and Conquer with Frequency Counting | O(n) | O(n) | General case. Count tasks and greedily split frequencies into groups of 3 and 2. |
| Dynamic Programming on Frequency | O(n) | O(n) | Useful when modeling the problem as a recurrence or demonstrating DP reasoning in interviews. |