LeetCode 2611 - Mice and Cheese

LeetCode Problem 2611

Difficulty: 🟡 Medium
Topics: Array, Greedy, Sorting, Heap (Priority Queue)

Solution

Problem Understanding

The problem gives us two arrays, reward1 and reward2, where each index represents a specific type of cheese. Every cheese must be eaten by exactly one of the two mice.

If cheese i is eaten by the first mouse, we gain reward1[i] points. If it is eaten by the second mouse, we gain reward2[i] points.

The key constraint is that the first mouse must eat exactly k cheeses. All remaining cheeses are automatically eaten by the second mouse.

Our goal is to maximize the total reward collected by both mice combined.

In other words, for every cheese we must decide which mouse should eat it. Since the first mouse can only eat exactly k cheeses, we want to carefully choose which k cheeses produce the greatest benefit when assigned to the first mouse instead of the second mouse.

The input size can be as large as 10^5, which immediately tells us that exponential or quadratic solutions are not feasible. We need an algorithm close to O(n log n) or better.

An important observation is that every cheese will always contribute some reward. If we initially assume that the second mouse eats every cheese, then the total score starts as:

sum(reward2)

Whenever we switch a cheese from the second mouse to the first mouse, the total score changes by:

reward1[i] - reward2[i]

This value represents the additional gain, or loss, from assigning cheese i to the first mouse instead of the second mouse.

The problem therefore becomes:

• Start with all cheeses assigned to mouse 2
• Choose exactly k cheeses with the largest gains
• Add those gains to the total

Important edge cases include:

• k = 0, meaning the second mouse eats everything
• k = n, meaning the first mouse eats everything
• Equal rewards where switching mice changes nothing
• Negative differences, where assigning a cheese to mouse 1 is actually worse, but we may still be forced to choose it because exactly k cheeses must go to mouse 1
• Very large arrays, requiring efficient sorting or heap usage

Approaches

Brute Force Approach

A brute force solution would try every possible selection of k cheeses for the first mouse.

For each combination:

1. Assign those k cheeses to mouse 1
2. Assign all remaining cheeses to mouse 2
3. Compute the total reward
4. Track the maximum value

This approach is guaranteed to find the optimal answer because it explores every valid assignment.

However, the number of ways to choose k cheeses from n is:

C(n, k)

This grows exponentially for large inputs. With n up to 100000, brute force becomes completely impossible.

Optimal Greedy Approach

The key insight is that we do not need to think about both mice independently.

Instead:

1. Assume mouse 2 eats everything initially
2. Compute the benefit of switching each cheese to mouse 1
3. Pick the k cheeses with the largest benefit

The benefit for cheese i is:

reward1[i] - reward2[i]

If this value is large and positive, assigning the cheese to mouse 1 is very advantageous.

If this value is negative, mouse 2 would prefer to eat it, but we may still need to assign some negative-difference cheeses if k is large.

By sorting these differences in descending order and selecting the top k, we guarantee the maximum possible total reward.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	O(k)	Tries every possible assignment
Optimal Greedy	O(n log n)	O(n)	Sorts reward differences and picks best k

Algorithm Walkthrough

1. Compute the baseline score by assuming the second mouse eats every cheese.

total = sum(reward2)

This gives us a convenient starting point because every cheese contributes something no matter what. 2. For every cheese, compute the additional gain obtained if the first mouse eats it instead.

gain = reward1[i] - reward2[i]

A positive value means mouse 1 is better for this cheese. A negative value means mouse 2 is better. 3. Store all gains in a list.

differences = []

4. Sort the gains in descending order.

The cheeses with the largest gains are the most valuable candidates for mouse 1. 5. Select the top k gains.

Since mouse 1 must eat exactly k cheeses, we choose the k largest differences. 6. Add those gains to the baseline total.

total += selected_gain

7. Return the final total reward.

Why it works

The algorithm works because every cheese contributes reward2[i] in the baseline configuration. Assigning a cheese to mouse 1 changes the total by exactly:

reward1[i] - reward2[i]

Since these changes are independent of each other, maximizing the final score is equivalent to choosing the k largest gains. Sorting guarantees that we select the best possible cheeses for mouse 1.

Python Solution

from typing import List

class Solution:
    def miceAndCheese(self, reward1: List[int], reward2: List[int], k: int) -> int:
        total_reward = sum(reward2)

        differences = []

        for r1, r2 in zip(reward1, reward2):
            differences.append(r1 - r2)

        differences.sort(reverse=True)

        for i in range(k):
            total_reward += differences[i]

        return total_reward

The implementation begins by calculating the total reward assuming the second mouse eats every cheese. This simplifies the logic because we only need to track how much extra value comes from switching cheeses to the first mouse.

Next, we compute the reward difference for every cheese. This difference represents the gain obtained by assigning that cheese to the first mouse instead of the second mouse.

After collecting all differences, we sort them in descending order so the best choices appear first.

Since the first mouse must eat exactly k cheeses, we add the top k differences to the baseline total.

Finally, we return the maximum achievable reward.

Go Solution

package main

import "sort"

func miceAndCheese(reward1 []int, reward2 []int, k int) int {
	totalReward := 0

	differences := make([]int, len(reward1))

	for i := 0; i < len(reward1); i++ {
		totalReward += reward2[i]
		differences[i] = reward1[i] - reward2[i]
	}

	sort.Slice(differences, func(i, j int) bool {
		return differences[i] > differences[j]
	})

	for i := 0; i < k; i++ {
		totalReward += differences[i]
	}

	return totalReward
}

The Go implementation follows the same logic as the Python version.

One notable difference is that Go requires explicit slice allocation for differences. Sorting is performed using sort.Slice with a custom comparator to achieve descending order.

Integer overflow is not a concern here because the maximum possible total reward is:

100000 * 1000 = 10^8

which safely fits within Go's int type on modern systems.

Worked Examples

Example 1

reward1 = [1,1,3,4]
reward2 = [4,4,1,1]
k = 2

Step 1: Baseline Total

Assume mouse 2 eats everything.

Cheese	reward2
0	4
1	4
2	1
3	1

total = 4 + 4 + 1 + 1 = 10

Step 2: Compute Differences

Cheese	reward1	reward2	Difference
0	1	4	-3
1	1	4	-3
2	3	1	2
3	4	1	3

Differences array:

[-3, -3, 2, 3]

Step 3: Sort Descending

[3, 2, -3, -3]

Step 4: Pick Top k = 2

3 + 2 = 5

Step 5: Add to Baseline

10 + 5 = 15

Final answer:

15

Example 2

reward1 = [1,1]
reward2 = [1,1]
k = 2

Step 1: Baseline Total

total = 1 + 1 = 2

Step 2: Compute Differences

Cheese	Difference
0	0
1	0

Step 3: Sort

[0, 0]

Step 4: Pick Top 2

0 + 0 = 0

Step 5: Final Total

2 + 0 = 2

Final answer:

2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting the differences dominates the runtime
Space	O(n)	The differences array stores one value per cheese

The algorithm performs a single pass to compute differences and a sort operation on n elements. Since sorting requires O(n log n) time, that becomes the overall complexity.

The additional memory usage comes from storing the differences array.

Test Cases

from typing import List

class Solution:
    def miceAndCheese(self, reward1: List[int], reward2: List[int], k: int) -> int:
        total_reward = sum(reward2)

        differences = []

        for r1, r2 in zip(reward1, reward2):
            differences.append(r1 - r2)

        differences.sort(reverse=True)

        for i in range(k):
            total_reward += differences[i]

        return total_reward

sol = Solution()

assert sol.miceAndCheese([1,1,3,4], [4,4,1,1], 2) == 15  # provided example
assert sol.miceAndCheese([1,1], [1,1], 2) == 2  # all equal rewards
assert sol.miceAndCheese([5], [3], 1) == 5  # single cheese, mouse 1 eats
assert sol.miceAndCheese([5], [3], 0) == 3  # single cheese, mouse 2 eats
assert sol.miceAndCheese([10,20,30], [1,1,1], 2) == 51  # strong preference for mouse 1
assert sol.miceAndCheese([1,1,1], [10,10,10], 1) == 21  # forced negative choice
assert sol.miceAndCheese([4,4,4], [4,4,4], 1) == 12  # all differences zero
assert sol.miceAndCheese([8,7,6], [5,5,5], 3) == 21  # k equals n
assert sol.miceAndCheese([8,7,6], [5,5,5], 0) == 15  # k equals zero
assert sol.miceAndCheese([2,9,1,8], [5,3,7,4], 2) == 29  # mixed differences

Test Summary

Test	Why
[1,1,3,4], [4,4,1,1], k=2	Validates the primary example
[1,1], [1,1], k=2	Tests equal rewards
Single element with k=1	Smallest non-trivial input
Single element with k=0	Ensures mouse 2 handling works
Large positive differences	Confirms greedy selection
Negative differences	Ensures exact k selections are enforced
All zero differences	Tests tie handling
k=n	Mouse 1 eats everything
k=0	Mouse 2 eats everything
Mixed values	General correctness validation

Edge Cases

Case 1: k = 0

When k is zero, the first mouse cannot eat any cheese. A buggy implementation might still try to access the sorted differences array or incorrectly assign cheeses.

This implementation handles the case naturally because the loop:

for i in range(k):

executes zero times. The algorithm simply returns:

sum(reward2)

which is correct.

Case 2: k = n

When k equals the number of cheeses, the first mouse must eat everything.

Some implementations accidentally leave certain cheeses assigned to mouse 2. Here, we add all differences back to the baseline:

sum(reward2) + sum(reward1 - reward2)

which simplifies to:

sum(reward1)

exactly as required.

Case 3: Negative Differences

Some cheeses may produce fewer points when assigned to mouse 1.

For example:

reward1 = [1]
reward2 = [10]

The difference is -9.

Even though this is worse, if k requires mouse 1 to eat the cheese, we must still choose it.

The implementation correctly handles this because it always selects exactly k differences after sorting, even if some are negative.