Minimum Rounds to Complete All Tasks — Problem & Solution
Minimum Rounds to Complete All Tasks solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Minimum Rounds to Complete All Tasks is a medium coding problem on arrays, hash table and greedy, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Greedy, Counting
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
tasks[i] is the difficulty level of the i-th task. In one round you finish either 2 or 3 tasks, and all tasks finished in the same round must have the same difficulty level.
Return the minimum number of rounds needed to finish every task, or -1 if it cannot be done.
Example 1
Input: tasks = [3,3,8,3,8,8,8,3,3]
Output: 4
Explanation: Level 3 has five tasks: a round of 3 and a round of 2. Level 8 has four tasks: two rounds of 2. Total 4.
Example 2
Input: tasks = [6,6,1]
Output: -1
Explanation: The single level-1 task can never be part of a round.
Example 3
Input: tasks = [9,9,9,9,9,9,9]
Output: 3
Explanation: Seven tasks: 3 + 2 + 2.
Constraints
1 <= tasks.length <= 10^51 <= tasks[i] <= 10^9
Hints for Minimum Rounds to Complete All Tasks
Hint 1
Different difficulty levels never share a round, so each level can be solved on its own.
Hint 2
For a level with
ctasks, what is the fewest rounds of size 2 or 3 adding up toc? When is it impossible?Hint 3
Only
c = 1is impossible. Otherwise use as many 3s as possible: the answer isceil(c / 3).
How to solve Minimum Rounds to Complete All Tasks
Group tasks by level and count each group. A count of 1 cannot be written as a sum of 2s and 3s; every other count c needs exactly ceil(c / 3) rounds.
Approach
- Count how many tasks each difficulty level has.
- If any level has exactly one task, return
-1. - Otherwise add
(c + 2) / 3(integer division) for every level's countc. - Return the total.
Why it works
No round can hold more than 3 tasks, so at least ceil(c / 3) rounds are needed. That many always suffice for c >= 2: if c % 3 == 0 use only 3s; if c % 3 == 2 add one round of 2; if c % 3 == 1 (so c >= 4) turn one 3 into two 2s — 3k + 1 = 3(k - 1) + 2 + 2, which is k + 1 = ceil(c / 3) rounds.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- A count of 1 makes the whole answer
-1, not just that level's contribution. - Greedy 'take a 3 whenever possible' fails on
c = 4(3 + 1); the closed form handles it. - Difficulty values go up to
10^9, so count with a hash map (or by sorting), not a direct-address array.
Reference solution
Python
from typing import List
from collections import Counter
def minimumRounds(tasks: List[int]) -> int:
rounds = 0
for c in Counter(tasks).values():
if c == 1:
return -1
rounds += (c + 2) // 3
return roundsJava
public static int minimumRounds(int[] tasks) {
Map<Integer, Integer> count = new HashMap<>();
for (int t : tasks) count.merge(t, 1, Integer::sum);
int rounds = 0;
for (int c : count.values()) {
if (c == 1) return -1;
rounds += (c + 2) / 3;
}
return rounds;
}C++
int minimumRounds(vector<int>& tasks) {
unordered_map<int, int> count;
for (int t : tasks) count[t]++;
int rounds = 0;
for (auto& kv : count) {
if (kv.second == 1) return -1;
rounds += (kv.second + 2) / 3;
}
return rounds;
}JavaScript
var minimumRounds = function(tasks) {
var count = new Map();
for (var i = 0; i < tasks.length; i++) {
var cur = count.get(tasks[i]);
count.set(tasks[i], (cur === undefined ? 0 : cur) + 1);
}
var rounds = 0;
var possible = true;
count.forEach(function(c) {
if (c === 1) possible = false;
rounds += Math.floor((c + 2) / 3);
});
return possible ? rounds : -1;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets