LeetCode 1815 - Maximum Number of Groups Getting Fresh Donuts

LeetCode Problem 1815

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Bit Manipulation, Memoization, Bitmask

Solution

Problem Understanding

This problem asks us to maximize the number of “happy” customer groups by choosing the best possible ordering of the groups.

The donut shop produces donuts in batches of exactly batchSize. A fresh batch starts only when the previous batch has been completely consumed. A group is considered happy if the very first customer in that group receives a donut from a completely fresh batch.

Each group contains groups[i] customers, and every customer consumes exactly one donut. Since groups must be served contiguously, a group may leave leftover donuts that affect the next group.

The key observation is that only the remainder of a group size modulo batchSize matters. Suppose batchSize = 5:

• A group of size 10 consumes exactly two full batches and leaves no leftovers.
• A group of size 12 leaves 2 donuts consumed into the next batch.
• A group of size 7 behaves exactly like a group of size 2 with respect to leftovers.

Therefore, instead of caring about the exact group sizes, we only care about:

groups[i] % batchSize

The goal is to reorder groups so that as many groups as possible begin when the current leftover amount is zero.

The constraints are important:

• batchSize <= 9
• groups.length <= 30

These limits are small enough to allow state compression dynamic programming. Since the batch size is tiny, the number of remainder categories is also tiny, which makes memoization feasible.

Several edge cases are important:

• Groups divisible by batchSize are always happy because they always start with a fresh batch.
• Multiple groups with complementary remainders can combine perfectly.
• The order matters heavily, so greedy choices may fail.
• Since there can be up to 30 groups, brute force permutation generation is impossible.

Approaches

Brute Force Approach

A direct brute force solution would try every possible ordering of the groups.

For each permutation:

1. Simulate serving groups in order.
2. Track the current leftover count modulo batchSize.
3. Count how many groups start when the remainder is zero.

This works because it explicitly checks every possible arrangement and therefore guarantees the optimal answer.

However, the complexity is catastrophic. With up to 30 groups, the number of permutations is:

30!

This is completely infeasible.

Even if we tried pruning, the search space would still be far too large.

Key Insight

The crucial observation is that only the remainder modulo batchSize matters.

Instead of tracking exact group sizes, we count how many groups belong to each remainder category:

remainder = group % batchSize

For example, if batchSize = 4, then every group belongs to one of:

0, 1, 2, 3

Now the problem becomes:

How do we arrange remainder categories to maximize the number of times
the running sum modulo batchSize becomes zero?

Because batchSize <= 9, we can use dynamic programming with memoization over the counts of remaining remainder groups.

The state consists of:

• How many groups of each remainder are left
• The current accumulated remainder

At each step, we choose the next remainder group to serve.

This transforms an impossible permutation problem into a manageable DP over compressed states.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n!)	O(n)	Tries every permutation
Optimal DP + Memoization	O(batchSize × states)	O(states)	Uses compressed remainder counts

Algorithm Walkthrough

Step 1: Convert Groups into Remainder Counts

For every group:

remainder = group % batchSize

Store how many groups belong to each remainder category.

For example:

batchSize = 3
groups = [1,2,3,4,5,6]

remainders:
1 % 3 = 1
2 % 3 = 2
3 % 3 = 0
4 % 3 = 1
5 % 3 = 2
6 % 3 = 0

So:

count[0] = 2
count[1] = 2
count[2] = 2

Step 2: Handle Remainder Zero Immediately

Any group whose remainder is zero always starts fresh.

Why?

Because it consumes an exact number of batches and leaves no leftovers.

So we immediately add:

happy = count[0]

These groups do not need to participate in the DP.

Step 3: Define the DP State

The recursive function tracks:

• Remaining counts of each remainder
• Current leftover remainder

Suppose:

current_remainder = 2

This means the current batch already has 2 donuts consumed modulo batchSize.

If the next group begins when:

current_remainder == 0

then that group is happy.

Step 4: Try Every Possible Next Remainder

For every remainder r that still has unused groups:

1. Use one group of remainder r
2. Update the new remainder:

new_remainder = (current_remainder + r) % batchSize

1. Recursively solve the smaller problem

If current_remainder == 0, then the chosen group contributes one happy group.

Step 5: Memoize States

Many recursive paths lead to identical states.

For example:

remaining counts = [0,2,1,0]
current remainder = 1

may appear repeatedly.

Memoization avoids recomputing these states.

Step 6: Return the Best Possible Result

Among all possible remainder choices, choose the one that maximizes the number of happy groups.

Why it works

The DP explores every valid ordering of remainder groups, but it compresses equivalent configurations into identical states. Since only the current remainder and remaining counts influence future behavior, the DP state fully captures all relevant information.

At every state, the algorithm considers every possible next choice and takes the maximum result. Therefore, by optimal substructure, the final answer is globally optimal.

Python Solution

from typing import List
from functools import lru_cache

class Solution:
    def maxHappyGroups(self, batchSize: int, groups: List[int]) -> int:
        remainder_count = [0] * batchSize
        
        for group in groups:
            remainder_count[group % batchSize] += 1
        
        happy_groups = remainder_count[0]
        
        counts = tuple(remainder_count[1:])
        
        @lru_cache(None)
        def dfs(state: tuple, current_remainder: int) -> int:
            best = 0
            
            for remainder in range(1, batchSize):
                index = remainder - 1
                
                if state[index] == 0:
                    continue
                
                next_state = list(state)
                next_state[index] -= 1
                
                gained = 1 if current_remainder == 0 else 0
                
                best = max(
                    best,
                    gained + dfs(
                        tuple(next_state),
                        (current_remainder + remainder) % batchSize
                    )
                )
            
            return best
        
        return happy_groups + dfs(counts, 0)

The implementation begins by counting how many groups belong to each remainder category. Since groups with remainder zero are automatically happy, they are added directly to the answer.

The remaining remainder counts are converted into a tuple so they can be used as part of the memoization key.

The recursive dfs function represents the optimal number of additional happy groups achievable from the current state. The function tries every available remainder category and recursively explores the resulting state.

Memoization is essential because many recursive branches reach identical configurations. Using @lru_cache ensures each state is solved only once.

The final answer combines:

• Automatically happy remainder-zero groups
• The optimal DP result

Go Solution

package main

func maxHappyGroups(batchSize int, groups []int) int {
	remainderCount := make([]int, batchSize)

	for _, group := range groups {
		remainderCount[group%batchSize]++
	}

	happyGroups := remainderCount[0]

	type State struct {
		counts []int
		remain int
	}

	memo := make(map[string]int)

	encode := func(counts []int, remain int) string {
		key := ""

		for _, value := range counts {
			key += string(rune(value + 'A'))
		}

		key += "#"
		key += string(rune(remain + 'A'))

		return key
	}

	var dfs func([]int, int) int

	dfs = func(counts []int, currentRemain int) int {
		key := encode(counts, currentRemain)

		if value, exists := memo[key]; exists {
			return value
		}

		best := 0

		for remainder := 1; remainder < batchSize; remainder++ {
			index := remainder - 1

			if counts[index] == 0 {
				continue
			}

			counts[index]--

			gained := 0
			if currentRemain == 0 {
				gained = 1
			}

			candidate := gained + dfs(
				counts,
				(currentRemain+remainder)%batchSize,
			)

			if candidate > best {
				best = candidate
			}

			counts[index]++
		}

		memo[key] = best
		return best
	}

	initialCounts := make([]int, batchSize-1)

	for i := 1; i < batchSize; i++ {
		initialCounts[i-1] = remainderCount[i]
	}

	return happyGroups + dfs(initialCounts, 0)
}

The Go solution follows the same logic as the Python implementation, but memoization is implemented manually using a map.

Because slices cannot be used directly as map keys, the counts array is serialized into a string representation. The DFS mutates the counts slice in place, then restores it after recursion, which avoids repeated slice allocations.

Go integers are fully sufficient because the answer never exceeds the number of groups.

Worked Examples

Example 1

Input:
batchSize = 3
groups = [1,2,3,4,5,6]

Step 1: Compute Remainders

Group	Remainder
1	1
2	2
3	0
4	1
5	2
6	0

So:

count[0] = 2
count[1] = 2
count[2] = 2

Initial happy groups:

happy = 2

Step 2: Start DFS

Initial state:

counts = (2,2)
current_remainder = 0

Since the remainder is zero, the next chosen group will be happy.

Suppose we choose remainder 2.

Action	New State
choose 2	counts=(2,1), remain=2

Happy groups gained:

+1

Next choose remainder 1.

(2 + 1) % 3 = 0

Now the next group again starts fresh.

Action	New State
choose 1	counts=(1,1), remain=0

Again we gain another happy group.

The DP explores all possibilities and finds the optimal arrangement:

[6,2,4,5,1,3]

Final answer:

4

Example 2

Input:
batchSize = 4
groups = [1,3,2,5,2,2,1,6]

Step 1: Compute Remainders

Group	Remainder
1	1
3	3
2	2
5	1
2	2
2	2
1	1
6	2

Counts:

count[0] = 0
count[1] = 3
count[2] = 4
count[3] = 1

The DFS explores all possible arrangements of these remainder groups.

One optimal ordering yields 4 happy groups.

Final answer:

4

Complexity Analysis

Measure	Complexity	Explanation
Time	O(batchSize × states)	Each DP state tries up to batchSize - 1 transitions
Space	O(states)	Memoization stores all visited states

The number of states depends on the possible remainder count combinations. Since batchSize <= 9 and groups.length <= 30, the total state space remains manageable.

The DP is efficient because it compresses all permutations that share the same remainder counts into a single memoized state.

Test Cases

solution = Solution()

# Provided example 1
assert solution.maxHappyGroups(3, [1,2,3,4,5,6]) == 4

# Provided example 2
assert solution.maxHappyGroups(4, [1,3,2,5,2,2,1,6]) == 4

# Single group divisible by batch size
assert solution.maxHappyGroups(5, [10]) == 1

# Single non-divisible group
assert solution.maxHappyGroups(5, [3]) == 1

# All groups perfectly divisible
assert solution.maxHappyGroups(4, [4,8,12]) == 3

# Complementary pairs
assert solution.maxHappyGroups(3, [1,2,1,2]) == 2

# Batch size 1, every group happy
assert solution.maxHappyGroups(1, [1,2,3,4]) == 4

# Many identical remainders
assert solution.maxHappyGroups(4, [1,1,1,1]) == 1

# Complex mixed case
assert solution.maxHappyGroups(5, [1,2,3,4,5,6,7,8,9,10]) >= 2

# Large values
assert solution.maxHappyGroups(9, [10**9, 10**9 - 1, 10**9 - 2]) >= 1

# Empty remainder interactions
assert solution.maxHappyGroups(7, [14,21,28]) == 3

Test Summary

Test	Why
[1,2,3,4,5,6]	Validates standard mixed remainders
[1,3,2,5,2,2,1,6]	Tests more complex DP branching
[10] with batchSize 5	Tests exact divisibility
[3] with batchSize 5	Tests single non-divisible group
[4,8,12]	All groups automatically happy
[1,2,1,2]	Tests complementary remainder pairing
batchSize = 1	Smallest possible batch size
[1,1,1,1]	Repeated same remainder
Mixed larger case	Stress tests recursion
Large group values	Confirms modulo compression
[14,21,28]	Multiple exact batches

Edge Cases

One important edge case occurs when every group size is divisible by batchSize. In this situation, every group automatically starts with a fresh batch because no leftovers remain after serving any group. A buggy implementation might still send these groups through the DP unnecessarily, increasing runtime and complexity. This implementation handles the case correctly by immediately counting all remainder-zero groups as happy before recursion begins.

Another tricky edge case is when batchSize = 1. Since every number modulo 1 equals 0, every group is happy. Some implementations accidentally create invalid DP states because there are no nonzero remainder categories. This solution handles the case naturally because the recursive state becomes empty and the DFS immediately returns 0.

A third important edge case involves many groups sharing the same remainder. For example:

batchSize = 4
groups = [1,1,1,1]

Naive greedy approaches may incorrectly assume each new group can become happy. In reality, the accumulated remainder cycles through nonzero states and only one group can start fresh. The memoized DP correctly evaluates all possible sequences and avoids overcounting.

Another subtle case occurs with extremely large group sizes such as 10^9. A naive implementation that tracks actual donut counts could overflow or become inefficient. This solution only stores:

group % batchSize

which keeps all computations small and efficient regardless of input magnitude.