Minimum Rounds to Complete All Tasks
MedPrompt
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.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach first sorts the input array. By sorting, all tasks of the same difficulty level become adjacent. We can then iterate through the sorted array once to count the occurrences of each task difficulty and calculate the rounds required.
Algorithm
- Sort the input array
tasks. - Initialize
totalRounds = 0. - Initialize a pointer
i = 0to traverse the array. - While
i < tasks.length: a. Initialize a second pointerj = i. b. Whilej < tasks.lengthandtasks[j] == tasks[i], incrementj. c. Calculate the count of the current task:count = j - i. d. Ifcount == 1, it's impossible to complete this task, so return -1. e. Calculate rounds for this group using the formula:rounds = (count + 2) / 3. f. AddroundstototalRounds. g. Move the main pointer to the next new task:i = j. - Return
totalRounds.
Walkthrough
The core idea is to group identical tasks together. Sorting is a straightforward way to achieve this. After sorting tasks, we can iterate from the beginning. We'll use a variable, say count, to keep track of the number of consecutive identical tasks. We traverse the array, and as long as the current task is the same as the previous one, we increment count. When we encounter a different task or reach the end of the array, it signifies the end of a group of identical tasks. At this point, we have the count for a specific difficulty level. We first check if count is 1. If it is, completing the tasks is impossible, so we return -1. Otherwise, we need to find the minimum rounds to complete count tasks. We can use groups of 2 or 3. To minimize the number of rounds, we should maximize the use of 3-task rounds. The number of rounds can be calculated with the formula (count + 2) / 3, which is equivalent to ceil(count / 3.0). We add this number to our total rounds and reset the count for the new task difficulty. We repeat this process until the entire array is traversed.
import java.util.Arrays; class Solution { public int minimumRounds(int[] tasks) { if (tasks.length == 0) { return 0; } Arrays.sort(tasks); int totalRounds = 0; int i = 0; while (i < tasks.length) { int j = i; while (j < tasks.length && tasks[j] == tasks[i]) { j++; } int count = j - i; if (count == 1) { return -1; } totalRounds += (count + 2) / 3; i = j; } return totalRounds; }}Complexity
Time
O(N log N), dominated by the sorting step. The subsequent scan of the array takes O(N) time.
Space
O(log N) or O(N), depending on the space used by the sorting algorithm implementation. For example, Java's `Arrays.sort` for primitives uses a dual-pivot quicksort which has an average space complexity of O(log N).
Trade-offs
Pros
Conceptually simple if you are familiar with sorting.
Doesn't require an auxiliary data structure like a hash map, potentially saving space if the sorting is in-place or has low space overhead.
Cons
The O(N log N) time complexity is suboptimal for this problem.
This is the optimal approach. It involves a single pass to count the frequency of each task difficulty using a hash map, followed by another pass through the map's entries to calculate the total rounds. This avoids the need for sorting.
Algorithm
- Create a
HashMap<Integer, Integer>to store task frequencies. - Iterate through the
tasksarray. For eachtask, update its frequency in the map. - Initialize
totalRounds = 0. - Iterate through the values (frequencies) of the hash map.
- For each
count: a. Ifcount == 1, return -1. b. Add(count + 2) / 3tototalRounds. - Return
totalRounds.
Walkthrough
The problem can be broken down by task difficulty. The number of rounds for one difficulty level is independent of the others. The total rounds is the sum of rounds for each difficulty. We can efficiently count the occurrences of each task difficulty using a hash map. We iterate through the tasks array once, and for each task, we increment its corresponding count in the map. After building the frequency map, we iterate through the counts (the values of the map). For each count, if it is 1, it's impossible to complete this task, so we return -1. Otherwise, we need to find the minimum number of rounds. The goal is to express count as 2*a + 3*b such that a+b is minimized. This is achieved by maximizing b, the number of 3-task rounds. A simple mathematical observation reveals the formula for the minimum rounds. If count % 3 == 0, we use count / 3 rounds. If count % 3 == 1, we can use (count/3 - 1) rounds of 3 and two rounds of 2. If count % 3 == 2, we can use count/3 rounds of 3 and one round of 2. All these cases can be unified by the formula (count + 2) / 3 using integer division, which is equivalent to ceil(count / 3.0). We sum up the rounds calculated for each distinct task difficulty to get the final answer.
import java.util.HashMap;import java.util.Map; class Solution { public int minimumRounds(int[] tasks) { Map<Integer, Integer> freq = new HashMap<>(); for (int task : tasks) { freq.put(task, freq.getOrDefault(task, 0) + 1); } int totalRounds = 0; for (int count : freq.values()) { if (count == 1) { return -1; } totalRounds += (count + 2) / 3; } return totalRounds; }}Complexity
Time
O(N), where N is the number of tasks. We iterate through the `tasks` array once to build the frequency map (O(N)) and then iterate through the unique tasks in the map (O(U), where U is the number of unique tasks, U <= N). The total time is O(N + U) = O(N).
Space
O(U), where U is the number of unique tasks. In the worst case, all tasks are unique, so the space complexity is O(N).
Trade-offs
Pros
Optimal time complexity of O(N).
The logic is clean and directly addresses the problem structure by grouping tasks first.
Cons
Requires extra space for the hash map, which could be up to O(N) in the worst case where all tasks are unique.
Solutions
Solution
class Solution {public int minimumRounds(int[] tasks) { Map<Integer, Integer> cnt = new HashMap<>(); for (int t : tasks) { cnt.merge(t, 1, Integer : : sum); } int ans = 0; for (int v : cnt.values()) { if (v == 1) { return -1; } ans += v / 3 + (v % 3 == 0 ? 0 : 1); } return ans; }}class Solution {public: int minimumRounds(vector<int> &tasks) { unordered_map<int, int> cnt; for (auto &t : tasks) { ++cnt[t]; } int ans = 0; for (auto &[_, v] : cnt) { if (v == 1) { return -1; } ans += v / 3 + (v % 3 != 0); } return ans; }};class Solution: def minimumRounds(self, tasks: List[int]) -> int: cnt = Counter(tasks) ans = 0 for v in cnt . values(): if v == 1: return - 1 ans += v // 3 + (v % 3 != 0) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.