Scale Engineer

Mice and Cheese

Med
#2391Time: 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.1 company
Patterns
Greedy
Algorithms
Sorting
Data structures
ArrayHeap (Priority Queue)
Companies
DoorDash

Prompt

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

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 diff of size n.
  • Iterate from i = 0 to n-1:
    • Calculate diff[i] = reward1[i] - reward2[i].
    • Add reward2[i] to totalScore. This sets up a baseline score assuming mouse 2 eats everything.
  • Sort the diff array in non-decreasing order.
  • Iterate from i = 0 to k-1:
    • Add diff[n - 1 - i] (the largest differences) to totalScore.
  • 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 large n if memory is constrained.

Solutions

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;  }}

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.

← Previous

Previous problem

Next →

Next problem