🌱 Keegan's Digital Garden

1815. Maximum Number of Groups Getting Fresh Donuts

3 min read

📝 Problem Details

💭What Were My Initial Thoughts?

~

🤔What Did I Struggle With?

- how to reduce problem space 
- how to determine order of groups to serve

💡 Explanation of Solution

1. Reduce Problem Space

  • instead of tracking the exact number of people in each group, track the remainder when divided by batchSize
  • this reduces the possible groups from 30 (max input) to just batchSize ⇐ 9

2. Greedy Matching Strategy

  • start by counting groups where group % batchSize == 0, as they are always “happy”
  • then, greedily pair groups (A,B) such that (A + B) % batchSize == 0 to maximize the number of happy groups
  • this effectively reduces the number of unpaired remainders

3. Dynamic Programming for Remaining Groups

  • after apply the greedy approach, there will most likely be some groups remaining
  • since larger combinations can be formed in multiple ways, use backtracking memoization (DP) to find the optimal way to combine them
  • the number of remaining groups is small, making DP efficient

⌛ Complexity Analysis

Time Complexity: O(n^b), where n is the number of groups and b is batchSize
- the greedy utilisation reduces b to b/2, which is not significant for the complexity analysis

Space Complexity: O(b)
- to store counts

💻 Implementation of Solution

class Solution {
private:
    unordered_map<vector<int>, int> dp;  // Memoization: Stores already computed results
public:
    // DFS function to maximize happy groups with backtracking and memoization
    int dfs(vector<int>& remainderCounts, int remainder) {
        // Check if the result for this state has already been computed
        auto it = dp.find(remainderCounts);
        if (it != dp.end())
            return it->second;
 
        int maxHappyGroups = 0;
        int batchSize = remainderCounts.size();
 
        // Try serving a group from each remainder category (except remainder 0)
        for (int i = 1; i < batchSize; ++i) {
            if (remainderCounts[i] > 0) {  // If there are groups with remainder `i`
                --remainderCounts[i];  // Use one such group
                // Calculate new remainder and count happy group if remainder becomes zero
                maxHappyGroups = max(maxHappyGroups, (remainder == 0) + dfs(remainderCounts, (batchSize + remainder - i) % batchSize));
                ++remainderCounts[i];  // Backtrack (undo the change)
            }
        }
 
        // Store the result in dp and return
        return dp[remainderCounts] = maxHappyGroups;
    }
 
    int maxHappyGroups(int batchSize, vector<int>& groups) {
        vector<int> remainderCounts(batchSize, 0);  // Store counts of remainders
        int happyGroups = 0;
 
        // Greedy Step: Directly count groups that are already happy
        for (int groupSize : groups) {
            int remainder = groupSize % batchSize;
            if (remainder == 0) {
                ++happyGroups;  // Group is happy as is
            } else if (remainderCounts[batchSize - remainder] > 0) {
                --remainderCounts[batchSize - remainder];  // Pair with complementary remainder
                ++happyGroups;
            } else {
                ++remainderCounts[remainder];  // Store for future pairing
            }
        }
 
        // Use DFS + Memoization to maximize additional happy groups
        return dfs(remainderCounts, 0) + happyGroups;
    }
};

Graph View