Mice and Cheese
MedPrompt
There are two mice and n different types of cheese, each type of cheese should be eaten by exactly one mouse.
A point of the cheese with index i (0-indexed) is:
reward1[i]if the first mouse eats it.reward2[i]if the second mouse eats it.
You are given a positive integer array reward1, a positive integer array reward2, and a non-negative integer k.
Return the maximum points the mice can achieve if the first mouse eats exactly k types of cheese.
Example 1:
Input: reward1 = [1,1,3,4], reward2 = [4,4,1,1], k = 2
Output: 15
Explanation: In this example, the first mouse eats the 2nd (0-indexed) and the 3rd types of cheese, and the second mouse eats the 0th and the 1st types of cheese.
The total points are 4 + 4 + 3 + 4 = 15.
It can be proven that 15 is the maximum total points that the mice can achieve.Example 2:
Input: reward1 = [1,1], reward2 = [1,1], k = 2
Output: 2
Explanation: In this example, the first mouse eats the 0th (0-indexed) and 1st types of cheese, and the second mouse does not eat any cheese.
The total points are 1 + 1 = 2.
It can be proven that 2 is the maximum total points that the mice can achieve.
Constraints:
1 <= n == reward1.length == reward2.length <= 1051 <= reward1[i], reward2[i] <= 10000 <= k <= n
Approaches
2 approaches with complexity analysis and trade-offs.
This approach is based on a greedy strategy. The core idea is to determine for each cheese, how much more (or less) reward we get by giving it to mouse 1 instead of mouse 2. This difference is reward1[i] - reward2[i]. To maximize the total score, we should give mouse 1 the k cheeses that provide the highest gain. We can find these k cheeses by calculating all n differences and sorting them.
Algorithm
- Initialize
totalScore = 0. - Create an integer array
diffof sizen. - Iterate from
i = 0ton-1:- Calculate
diff[i] = reward1[i] - reward2[i]. - Add
reward2[i]tototalScore. This sets up a baseline score assuming mouse 2 eats everything.
- Calculate
- Sort the
diffarray in non-decreasing order. - Iterate from
i = 0tok-1:- Add
diff[n - 1 - i](the largest differences) tototalScore.
- Add
- Return
totalScore.
Walkthrough
First, we can calculate an initial total score by assuming mouse 2 eats all n cheeses. This score would be the sum of all elements in reward2. Now, we need to select exactly k cheeses to be "switched" from mouse 2 to mouse 1. When we switch cheese i, the total score changes by reward1[i] - reward2[i]. To maximize the final score, we must choose the k cheeses that have the largest values for this difference. The algorithm sorts all these differences and picks the top k to add to the base score.
import java.util.Arrays; class Solution { public int miceAndCheese(int[] reward1, int[] reward2, int k) { int n = reward1.length; int[] diff = new int[n]; int totalScore = 0; for (int i = 0; i < n; i++) { // The gain in score if mouse 1 eats cheese i instead of mouse 2 diff[i] = reward1[i] - reward2[i]; // Start with the score as if mouse 2 eats all cheese totalScore += reward2[i]; } // Sort the differences to find the k largest gains Arrays.sort(diff); // Add the k largest gains to the total score // These correspond to the k cheeses mouse 1 should eat for (int i = 0; i < k; i++) { totalScore += diff[n - 1 - i]; } return totalScore; }}Complexity
Time
O(n log n) - The dominant operation is sorting the `diff` array of size `n`. The initial loops to calculate differences and the base score take O(n), and the final loop takes O(k). Thus, the total time complexity is O(n + n log n + k) = O(n log n).
Space
O(n) - We need an auxiliary array `diff` of size `n` to store the differences.
Trade-offs
Pros
Simple and straightforward to understand and implement.
Correctly solves the problem based on a clear greedy choice.
Cons
Not the most efficient solution. The
O(n log n)time complexity can be improved upon.Requires
O(n)extra space, which might be a concern for very largenif memory is constrained.
This approach also uses the same greedy strategy of finding the k cheeses with the highest reward1[i] - reward2[i] difference. However, instead of sorting the entire array of differences, we can find the k largest elements more efficiently using a min-heap (implemented as a PriorityQueue in Java). This is a classic "Top K" problem pattern, which avoids the cost of a full sort.
Algorithm
- If
k == 0, return the sum ofreward2. - Create a min-priority queue
pq. - Iterate from
i = 0ton-1:- Calculate
diff = reward1[i] - reward2[i]. - Add
difftopq. - If
pq.size() > k, remove the minimum element frompqusingpq.poll().
- Calculate
- Initialize
totalScore = 0. - Add all elements from
reward2tototalScore. - Add all elements remaining in
pq(which are the top k differences) tototalScore. - Return
totalScore.
Walkthrough
The logic remains the same: start with a base score where mouse 2 eats everything, and then add the gains from giving the k most beneficial cheeses to mouse 1. The key difference is how we find these k most beneficial cheeses. We maintain a min-heap of size k. We iterate through all n differences. For each difference, we add it to the heap. If the heap's size grows beyond k, we remove the smallest element. This ensures that after iterating through all n differences, the heap contains exactly the k largest differences. We then add these k differences to our base score.
import java.util.PriorityQueue; class Solution { public int miceAndCheese(int[] reward1, int[] reward2, int k) { int n = reward1.length; // A min-heap to efficiently find the k largest differences. PriorityQueue<Integer> topKDiffs = new PriorityQueue<>(); for (int i = 0; i < n; i++) { int diff = reward1[i] - reward2[i]; topKDiffs.offer(diff); // Keep the heap size at most k if (topKDiffs.size() > k) { topKDiffs.poll(); } } // Base score: mouse 2 eats everything. int totalScore = 0; for (int r : reward2) { totalScore += r; } // Add the k largest differences from the heap. while (!topKDiffs.isEmpty()) { totalScore += topKDiffs.poll(); } return totalScore; }}Complexity
Time
O(n log k) - We iterate through `n` cheeses. For each cheese, we perform an operation on the priority queue (offer/poll), which takes `O(log k)` time since the heap's size is at most `k`. The initial sum takes O(n) and the final sum takes O(k). Thus, the total time complexity is O(n * log k).
Space
O(k) - The priority queue stores at most `k` elements. This is an improvement over the sorting approach's `O(n)` space.
Trade-offs
Pros
More efficient than the sorting approach, with a time complexity of
O(n log k).More space-efficient, requiring only
O(k)extra space, which is beneficial whenkis much smaller thann.
Cons
Slightly more complex to implement than the sorting approach due to the use of a priority queue.
Solutions
Solution
class Solution {public int miceAndCheese(int[] reward1, int[] reward2, int k) { int n = reward1.length; Integer[] idx = new Integer[n]; for (int i = 0; i < n; ++i) { idx[i] = i; } Arrays.sort(idx, (i, j)->reward1[j] - reward2[j] - (reward1[i] - reward2[i])); int ans = 0; for (int i = 0; i < k; ++i) { ans += reward1[idx[i]]; } for (int i = k; i < n; ++i) { ans += reward2[idx[i]]; } return ans; }}class Solution {public: int miceAndCheese(vector<int> &reward1, vector<int> &reward2, int k) { int n = reward1.size(); vector<int> idx(n); iota(idx.begin(), idx.end(), 0); sort(idx.begin(), idx.end(), [&](int i, int j) { return reward1[j] - reward2[j] < reward1[i] - reward2[i]; }); int ans = 0; for (int i = 0; i < k; ++i) { ans += reward1[idx[i]]; } for (int i = k; i < n; ++i) { ans += reward2[idx[i]]; } return ans; }};class Solution: def miceAndCheese(self, reward1: List[int], reward2: List[int], k: int) -> int: n = len(reward1) idx = sorted(range(n), key=lambda i: reward1[i] - reward2[i], reverse=True) return sum(reward1[i] for i in idx[: k]) + sum(reward2[i] for i in idx[k:])Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.