🌱 Keegan's Digital Garden

2244. Minimum Rounds to Complete All Tasks

2 min read

📝 Problem Details

💭What Were My Initial Thoughts?

- create an unordered map where we store the frequency counts fo each element in the array
- init a counter/rounds variable
- iterate through the map
	- while the frequency is >0
		- if the freq == 1 return -1 since its a failed result
		- greedily decrement the freq by 3 if possible
		- try decrement the freq by 2 if the above isnt possible
-return the count / number of rounds

🤔What Did I Struggle With?

- this doesnt exactly take into account certain edge cases
	- if we have an element with a freq of 4
	- we greedily decrease it by 3, leaving 1
	- the next iteration returns -1 since its considered impossible at this state
	- but if we instead decrememnt it by 2 first, and then 2 again, it is possible

💡 Explanation of Solution

- the solution is largely the same as the initial approach except instead of the while loop, we will do a single calculation to greedily determine the number of rounds required for each element 

use `(freq + 2) / 3` to calculate the ceiling of divide freq by 3

⌛ Complexity Analysis

Time Complexity: O(n)
- n iterations of elements to construct the frequency map
- k iterations of elements through each unique element in the map

Space Complexity: O(n)
- for the construction of the frequency map

💻 Implementation of Solution

class Solution {
 
public:
    int minimumRounds(vector<int>& tasks) {
        unordered_map<int, int> map;
 
        for(int i = 0; i < tasks.size(); i++) {
            map[tasks[i]]++;
        }
 
        int rounds = 0;
        // Iterate through each unique task difficulty
        for (auto it = map.begin(); it != map.end(); it++) {
            int freq = it->second;
 
            // Early exit condition: If the frequency is 1, it's impossible
            if (freq == 1) return -1;
 
            // Calculate the minimum rounds needed for this frequency
            rounds += (freq + 2) / 3;  // Greedy method: ceil(freq / 3)
        }
 
        return rounds;
    }
};

Graph View