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.
This approach involves breaking down the problem into smaller subproblems, solving each of them independently, and combining their results in an efficient way. It often uses recursion to handle each subproblem.
This C code uses a recursive function to implement the divide and conquer strategy. It divides the problem into two halves, solves each recursively, and then combines their solutions.
Time Complexity: T(n) = 2T(n/2) + O(n) => O(n log n)
Space Complexity: O(log n) due to recursion stack space.
This approach involves solving complex problems by breaking them into simpler overlapping subproblems, storing the results of subproblems to avoid redundant calculations, and constructing a solution from these stored results.
This C code uses dynamic programming to store results of subproblems. This avoids redundant computations, especially useful in fibonacci-style computations.
Time Complexity: O(n)
Space Complexity: O(n)
We use a hash table to count the number of tasks for each difficulty level. Then we traverse the hash table. For each difficulty level, if the number of tasks is 1, then it is impossible to complete all tasks, so we return -1. Otherwise, we calculate the number of rounds needed to complete tasks of this difficulty level and add it to the answer.
Finally, we return the answer.
The time complexity is O(n), and the space complexity is O(n), where n is the length of the tasks array.
| Approach | Complexity |
|---|---|
| Divide and Conquer Approach | Time Complexity: T(n) = 2T(n/2) + O(n) => O(n log n) |
| Dynamic Programming Approach | Time Complexity: O(n) |
| Hash Table | — |
| 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. |
Minimum Rounds to Complete All Tasks : Explanation ➕ Live Coding 🧑🏻💻👩🏻💻 • codestorywithMIK • 7,032 views views
Watch 9 more video solutions →Practice Minimum Rounds to Complete All Tasks with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor