Minimum Rounds to Complete All Tasks

Medium
1151.

Minimum Rounds to Complete All Tasks

Minimum Rounds to Complete All Tasks is a medium coding problem on arrays, hash table and greedy, asked in Amazon and Google interviews.

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^5
  • 1 <= tasks[i] <= 10^9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} tasks
 * @return {number}
 */
var minimumRounds = function(tasks) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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^5
  • 1 <= tasks[i] <= 10^9

Hints for Minimum Rounds to Complete All Tasks

  1. Hint 1

    Different difficulty levels never share a round, so each level can be solved on its own.

  2. Hint 2

    For a level with c tasks, what is the fewest rounds of size 2 or 3 adding up to c? When is it impossible?

  3. Hint 3

    Only c = 1 is impossible. Otherwise use as many 3s as possible: the answer is ceil(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

  1. Count how many tasks each difficulty level has.
  2. If any level has exactly one task, return -1.
  3. Otherwise add (c + 2) / 3 (integer division) for every level's count c.
  4. 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 rounds

Java

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