2244. Minimum Rounds to Complete All Tasks

Leetcode 2244 problem

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;
    }
}