Mice and Cheese solution and explanation
9 more videos on this problem
2611. Mice and Cheese | Weekly Contest 339 | LeetCode 2611Bro Coders · 8:55 · 2K views
Leetcode 2611: Mice and CheeseAlgorithms Casts · 11:07 · 1K views
Leetcode Problem 2611. Mice and Cheese | Weekly Contest 339 | OffCampus PhodengeOffCampus Phodenge | Aman Chowdhury · 13:58 · 912 views
LeetCode Weekly Contest 339 | 6364. Mice and Cheese | PythonBayu Aji · 4:39 · 776 views
2611. Mice and Cheese (Leetcode Medium)Programming Live with Larry · 6:59 · 671 views
Mice and Cheese | Weekly Contest 339codingMohan · 9:15 · 651 views
Leetcode Weekly contest 339 - Medium - Mice and CheesePrakhar Agrawal · 8:33 · 617 views
6364. Mice and Cheese - LEETCODE WEEKLY CONTEST 339 (Logic explained in details)Joyjit Codes · 4:00 · 597 views
Leetcode 2611 Mice and Cheese HindiThinkCode · 10:18 · 528 views
Leetcode 2611 Mice and Cheese (Java) - Leetcode Weekly Contest 339 - Beats 100%TheAnalyticGuy · 8:35 · 340 views
The problem
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
Approach overview
Problem Overview: Two mice eat cheese from the same set of plates. If mouse1 eats cheese i you gain reward1[i]; if mouse2 eats it you gain reward2[i]. Exactly k cheeses must go to mouse1 and the rest to mouse2. The goal is maximizing total reward.
Approach 1: Brute Force Assignment (Exponential Time)
Try every combination of choosing k indices for mouse1 and assign the remaining cheeses to mouse2. For each combination, compute the total reward by summing reward1 for chosen indices and reward2 for the rest. This guarantees the optimal answer but requires evaluating C(n, k) possibilities, leading to O(2^n) time in the worst case and O(1) extra space. This approach mainly helps understand the decision structure: each cheese represents a binary choice.
Approach 2: Greedy with Sorting by Difference (O(n log n))
The key insight is comparing how much extra reward you gain if mouse1 eats a cheese instead of mouse2. For each index compute the difference diff = reward1[i] - reward2[i]. A large positive difference means mouse1 should strongly prefer that cheese, while a negative value means mouse2 should take it. Sort cheeses by this difference in descending order and assign the first k cheeses to mouse1. The rest automatically go to mouse2. Sorting costs O(n log n) time and the final summation is O(n), with O(n) space if you store the differences. This greedy ordering works because every assignment decision is independent once you rank the relative benefit.
Approach 3: Greedy with Heap / Priority Queue (O(n log k))
Instead of sorting the entire list, push differences (reward1[i] - reward2[i]) into a heap (priority queue). Maintain the top k largest differences using a min-heap of size k. First assume mouse2 eats every cheese and sum reward2. Then add the best k improvements from the heap to convert those plates to mouse1. Heap operations cost O(log k), producing O(n log k) time and O(k) space. This version is useful when k is much smaller than n.
The core idea is a classic greedy optimization over an array: evaluate the gain of choosing one option over another, rank those gains, and pick the best ones.
Recommended for interviews: The greedy difference strategy with sorting is the expected solution. Start by explaining the brute force choice model, then show how computing reward1[i] - reward2[i] converts the problem into selecting the top k gains. This demonstrates both correctness reasoning and practical optimization.
Approach 1: Greedy Approach with Sorting by Difference
We need to balance between the two mice such that the total points collected are maximized. The key idea is to sort the cheeses based on the difference between the rewards for each mouse.
Calculate the difference between the rewards for each cheese (reward1[i] - reward2[i]) and use this difference to determine which mouse gets which cheese. The first mouse should get the 'k' cheeses with the highest positive differences.
def maxPoints(reward1, reward2, k):
differences = sorted([(reward1[i] - reward2[i], i) for i in range(len(reward1))], reverse=True)
total_points = sum(reward2)
for i in range(k):
diff, index = differences[i]
total_points += diff
return total_points
reward1 = [1,1,3,4]
reward2 = [4,4,1,1]
k = 2
print(maxPoints(reward1, reward2, k))import java.util.Arrays;
public class MiceAndCheese {
public static int maxPoints(int[] reward1, int[] reward2, int k) {
int n = reward1.length;
int[][] differences = new int[n][2];
int totalPoints = 0;
for (int i = 0; i < n; i++) {
differences[i][0] = reward1[i] - reward2[i];
differences[i][1] = i;
totalPoints += reward2[i];
}
Arrays.sort(differences, (a, b) -> b[0] - a[0]);
for (int i = 0; i < k; i++) {
totalPoints += differences[i][0];
}
return totalPoints;
}
public static void main(String[] args) {
int[] reward1 = {1, 1, 3, 4};
int[] reward2 = {4, 4, 1, 1};
int k = 2;
System.out.println(maxPoints(reward1, reward2, k));
}
}#include <iostream>
#include <vector>
#include <algorithm>
int maxPoints(std::vector<int>& reward1, std::vector<int>& reward2, int k) {
int n = reward1.size();
std::vector<std::pair<int, int>> differences(n);
int totalPoints = 0;
for (int i = 0; i < n; i++) {
differences[i] = {reward1[i] - reward2[i], i};
totalPoints += reward2[i];
}
std::sort(differences.rbegin(), differences.rend());
for (int i = 0; i < k; i++) {
totalPoints += differences[i].first;
}
return totalPoints;
}
int main() {
std::vector<int> reward1 = {1, 1, 3, 4};
std::vector<int> reward2 = {4, 4, 1, 1};
int k = 2;
std::cout << maxPoints(reward1, reward2, k) << std::endl;
return 0;
}function maxPoints(reward1, reward2, k) {
const differences = reward1.map((r1, i) => [r1 - reward2[i], i]);
let totalPoints = reward2.reduce((acc, curr) => acc + curr, 0);
differences.sort((a, b) => b[0] - a[0]);
for (let i = 0; i < k; i++) {
totalPoints += differences[i][0];
}
return totalPoints;
}
const reward1 = [1, 1, 3, 4];
const reward2 = [4, 4, 1, 1];
const k = 2;
console.log(maxPoints(reward1, reward2, k));#include <stdio.h>
#include <stdlib.h>
int compare(const void* a, const void* b) {
return (*(int*)b - *(int*)a);
}
int maxPoints(int* reward1, int* reward2, int n, int k) {
int differences[n];
int totalPoints = 0;
for (int i = 0; i < n; i++) {
differences[i] = reward1[i] - reward2[i];
totalPoints += reward2[i];
}
qsort(differences, n, sizeof(int), compare);
for (int i = 0; i < k; i++) {
totalPoints += differences[i];
}
return totalPoints;
}
int main() {
int reward1[] = {1, 1, 3, 4};
int reward2[] = {4, 4, 1, 1};
int k = 2;
printf("%d\n", maxPoints(reward1, reward2, 4, k));
return 0;
}using System;
using System.Linq;
public class MiceAndCheese {
public static int MaxPoints(int[] reward1, int[] reward2, int k) {
int n = reward1.Length;
var differences = reward1.Select((r1, i) => new { Diff = r1 - reward2[i], Index = i }).ToArray();
int totalPoints = reward2.Sum();
Array.Sort(differences, (a, b) => b.Diff.CompareTo(a.Diff));
for (int i = 0; i < k; i++) {
totalPoints += differences[i].Diff;
}
return totalPoints;
}
public static void Main() {
int[] reward1 = {1, 1, 3, 4};
int[] reward2 = {4, 4, 1, 1};
int k = 2;
Console.WriteLine(MaxPoints(reward1, reward2, k));
}
}This solution calculates the difference between the rewards for each cheese and sorts these differences in descending order. The first 'k' cheeses with the highest differences are selected for the first mouse, thereby increasing the total points from the base sum of reward2.
Time Complexity: O(n log n) due to the sorting step.
Space Complexity: O(n) for storing the differences.
Approach 2: Greedy + Sort
We can first give all the cheese to the second mouse. Next, consider giving k pieces of cheese to the first mouse. How should we choose these k pieces of cheese? Obviously, if we give the i-th piece of cheese from the second mouse to the first mouse, the change in the score is reward1[i] - reward2[i]. We hope that this change is as large as possible, so that the total score is maximized.
Therefore, we sort the cheese in decreasing order of reward1[i] - reward2[i]. The first k pieces of cheese are eaten by the first mouse, and the remaining cheese is eaten by the second mouse to obtain the maximum score.
Time complexity O(n times log n), space complexity O(n). Where n is the number of cheeses.
function miceAndCheese(reward1: number[], reward2: number[], k: number): number {
const n = reward1.length;
const idx = Array.from({ length: n }, (_, i) => i);
idx.sort((i, j) => reward1[j] - reward2[j] - (reward1[i] - reward2[i]));
let ans = 0;
for (let i = 0; i < k; ++i) {
ans += reward1[idx[i]];
}
for (let i = k; i < n; ++i) {
ans += reward2[idx[i]];
}
return ans;
}func miceAndCheese(reward1 []int, reward2 []int, k int) (ans int) {
n := len(reward1)
idx := make([]int, n)
for i := range idx {
idx[i] = i
}
sort.Slice(idx, func(i, j int) bool {
i, j = idx[i], idx[j]
return reward1[j]-reward2[j] < reward1[i]-reward2[i]
})
for i := 0; i < k; i++ {
ans += reward1[idx[i]]
}
for i := k; i < n; i++ {
ans += reward2[idx[i]]
}
return
}Approach 3: Default Approach
function miceAndCheese(reward1: number[], reward2: number[], k: number): number {
const n = reward1.length;
let ans = 0;
for (let i = 0; i < n; ++i) {
ans += reward2[i];
reward1[i] -= reward2[i];
}
reward1.sort((a, b) => b - a);
for (let i = 0; i < k; ++i) {
ans += reward1[i];
}
return ans;
}func miceAndCheese(reward1 []int, reward2 []int, k int) (ans int) {
for i, x := range reward2 {
ans += x
reward1[i] -= x
}
sort.Ints(reward1)
n := len(reward1)
for i := 0; i < k; i++ {
ans += reward1[n-i-1]
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Approach with Sorting by Difference | Time Complexity: O(n log n) due to the sorting step. |
| Greedy + Sort | – |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Assignment | O(2^n) | O(1) | Conceptual understanding or very small n |
| Greedy with Sorting by Difference | O(n log n) | O(n) | Standard optimal solution used in interviews |
| Greedy with Heap (Priority Queue) | O(n log k) | O(k) | Better when k is much smaller than n |
Frequently asked questions
Is Mice and Cheese easy or hard?
Mice and Cheese is rated Medium difficulty. The challenge lies in recognizing the greedy insight that the decision depends on reward1[i] - reward2[i], which converts the problem into selecting the top k gains.
How to solve Mice and Cheese in O(n)?
A strict O(n) solution is not typical because selecting the top k differences usually requires sorting or a heap. The practical optimal approach is O(n log n) using sorting, or O(n log k) using a priority queue to track the best k reward improvements.
What is the best approach for Mice and Cheese?
The optimal strategy is a greedy approach based on reward differences. Compute reward1[i] - reward2[i] for every cheese, sort the differences in descending order, and assign the top k cheeses to mouse1. This guarantees the largest total reward and runs in O(n log n) time with O(n) space.
What data structure is used in Mice and Cheese?
The solution primarily uses arrays and a greedy strategy. Sorting is commonly used to rank reward differences, while an alternative implementation uses a heap (priority queue) to maintain the top k candidates.
What is the time complexity of Mice and Cheese?
The typical optimal solution uses sorting, giving O(n log n) time complexity and O(n) space. A heap-based variant can reduce the complexity to O(n log k) if you only maintain the top k reward differences.
Mice and Cheese Python or Java solution approach?
Both Python and Java implementations follow the same idea: compute reward1[i] - reward2[i], sort indices by this difference, assign the first k to mouse1, and sum the rest for mouse2. The algorithm runs in O(n log n) time regardless of language.
Is Mice and Cheese asked at Google, Amazon, or Meta?
Problems based on greedy selection and difference sorting appear frequently in interviews at companies like Amazon, Google, and Meta. While the exact problem may vary, the pattern of choosing top k gains from two options is a common interview theme.