Question
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 <= 105
1 <= tasks[i] <= 109
Intuition
In each round, we can complete either 2 or 3 tasks with the same difficulty. We actually need to find the minimum number of rounds, so it's ideal to complete 3 tasks because it will reduce the number of rounds.
Example: say we have 6 x tasks. To get the minimum, it is always better to complete 3, 3 tasks than 2, 2, 2 tasks.
Approach
So first of all we actually need to consider the count and a hashmap can be best used for this scenario. After taking the count and storing it in the hashmap, iterate through the hashmap and check whether the count is < 2. This is our base condition and we can return -1 right away.
Otherwise, just try to find how many 3 jobs + 3 jobs + …. + 2 jobs count.
This can be achieved by (currentCount + 2) / 3 and adding this result to the minimum round.
Complexity
- Time complexity: O(n) + O(n) because we are traversing through the array first and then through the hashmap which can have approx. n elements in the worst case.
- Space complexity: We use an extra hashmap to store the count of each task; it can be n in the worst case. So space complexity will be O(n).
Code
class Solution {
public int minimumRounds(int[] tasks) {
int length = tasks.length;
if (tasks == null || length == 0) {
return 0;
}
int roundCount = 0;
Map<Integer, Integer> taskCount = new HashMap<>();
for (int task : tasks) {
taskCount.put(task, taskCount.getOrDefault(task, 0) + 1);
}
for (Integer taskKey : taskCount.keySet()) {
int currentKeyCount = taskCount.get(taskKey);
if (currentKeyCount < 2) {
return -1;
}
roundCount += (currentKeyCount + 2) / 3;
}
return roundCount;
}
}
Please feel free to discuss about any different idea or different approach.
Top comments (3)
Good solution Rohith! Here is mine. First I sort the array and then I keep track how many are with the same size and then do the math.
Nice to know about a different approach. Will the TC will be O(nlogn) due to sorting?
Yes, the sorting will take O(nlogn) the rest would be O(n). On this small inputs like this the performance would be hardly noticeable. However this is what I got from LeetCode using my solution.