Skip to main content
Talentd

Mice and Cheese - Solution & Explanation

MediumArrayGreedySortingHeap (Priority Queue)15 min readAsked at: DoorDash
Practice this problem

Problem Statement

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 <= 105
  • 1 <= reward1[i], reward2[i] <= 1000
  • 0 <= 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.

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.

Code

PythonJavaC++C#JavaScriptC

Python

Java

C++

C#

JavaScript

C

Complexity

Time Complexity: O(n log n) due to the sorting step.
Space Complexity: O(n) for storing the differences.

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy Approach with Sorting by Difference

Time Complexity: O(n log n) due to the sorting step.
Space Complexity: O(n) for storing the differences.

Greedy + Sort—
Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force AssignmentO(2^n)O(1)Conceptual understanding or very small n
Greedy with Sorting by DifferenceO(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

Video Solution

2611. Mice and Cheese | Weekly Contest 339 | LeetCode 2611 • Bro Coders • 2,588 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Mice and Cheese with our built-in code editor and test cases.

Practice on FleetCode
Previous

House Robber