# Mice and Cheese
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/mice-and-cheese)
Canonical: https://scaleengineer.com/dsa/problems/mice-and-cheese
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Heap (Priority Queue)
**Companies:** [DoorDash](https://scaleengineer.com/companies/doordash)
---
## 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 <= 105`
* `1 <= reward1[i], reward2[i] <= 1000`
* `0 <= k <= n`

# Approaches
## Sorting the Differences
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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`.

## Using a Priority Queue (Min-Heap)
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.
**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.
**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 when `k` is much smaller than `n`.
**Cons:** Slightly more complex to implement than the sorting approach due to the use of a priority queue.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
*   If `k == 0`, return the sum of `reward2`.
*   Create a min-priority queue `pq`.
*   Iterate from `i = 0` to `n-1`:
    *   Calculate `diff = reward1[i] - reward2[i]`.
    *   Add `diff` to `pq`.
    *   If `pq.size() > k`, remove the minimum element from `pq` using `pq.poll()`.
*   Initialize `totalScore = 0`.
*   Add all elements from `reward2` to `totalScore`.
*   Add all elements remaining in `pq` (which are the top k differences) to `totalScore`.
*   Return `totalScore`.

# Solutions
### Java

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

```

### CPP

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

```

### Python

```python
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:])

```