Hey fellow developers π
Welcome back to our DSA learning series!
In this series, we focus on problems that look simple at first but often confuse beginners because of tricky constraints and edge cases. We are learning DSA just like you, so the goal is always to break problems down logically instead of jumping straight into the code.
In this post, we are going to discuss a greedy-based problem that helps you understand how frequency counting and optimal grouping work together to minimize operations.
Task Rules
- In one round, you can complete either 2 or 3 tasks of the same difficulty
- You must complete all tasks
- If itβs not possible (for example, only one task of a difficulty is left), return -1
Example
Input
tasks = [2,2,3,3,2,4,4,4,4,4]
Explanation
We can complete the tasks in the following way:
- Round 1 β 3 tasks of difficulty 2
- Round 2 β 2 tasks of difficulty 3
- Round 3 β 3 tasks of difficulty 4
- Round 4 β 2 tasks of difficulty 4
So the minimum number of rounds required is 4.
Approach (Greedy + HashMap)
Since we need to group tasks by difficulty, the first thing that comes to mind is a HashMap.
Step 1: Count frequency of each difficulty
Store:
difficulty (key)β number of occurrences (Count)
Step 2: Calculate rounds for each difficulty
For each difficulty count:
- If count == 1 β β not possible β return -1
- If count % 3 == 0 β use all groups of 3
Otherwise β use as many groups of 3 as possible and one group of 2
Why this works?
A group of 3 is more efficient than 2 (fewer rounds)
For any remainder:
- 4 = 2 + 2
- 5 = 3 + 2
- 8 = 3 + 3 + 2 So we just add one extra round when it's not divisible by 3.
Code (Java)
class Solution {
public int minimumRounds(int[] tasks) {
HashMap<Integer, Integer> mp = new HashMap<>();
// Count frequency of each difficulty
for (int task : tasks) {
mp.put(task, mp.getOrDefault(task, 0) + 1);
}
int rounds = 0;
// Calculate rounds
for (int key : mp.keySet()) {
int count = mp.get(key);
if (count == 1) {
return -1;
}
if (count % 3 == 0) {
rounds += count / 3;
} else {
rounds += (count / 3) + 1;
}
}
return rounds;
}
}
Complexity Analysis
Time Complexity: O(n)
- One loop to build the HashMap β O(n)
- One loop over unique difficulties β at most O(n)
- HashMap operations (get, put) are O(1) on average
Overall: O(n)
Space Complexity: O(n)
HashMap stores frequencies of tasks
Why Time Complexity Is Linear?
Because:
- Each task is processed once
- HashMap operations take constant time
- No nested loops
So total operations grow linearly with input size.
If you found this helpful, give it a like π and share it with your fellow coders!
Happy coding !!!
Top comments (0)