Mice and Cheese — Editorial

Opening the reading…

Intuitionwhy the assignment becomes a fixed-size choice

Start with the only assignment that gives every cheese a default owner: let mouse two eat all n cheeses. This gives a base score equal to the sum of reward2[i]. The requirement that mouse one eats exactly k cheeses now means you must choose exactly k cheeses to move away from that baseline.

Moving cheese i from mouse two to mouse one changes the total by reward1[i] - reward2[i]. A positive difference improves the score, a negative difference reduces it, and a zero difference leaves it unchanged. Because every cheese contributes independently and the number of moves is fixed, the best assignment takes the k largest differences. No later choice can compensate for skipping a larger difference in favor of a smaller one.

Approachturn each possible reassignment into a gain

Treat mouse two as the initial owner of every cheese and add all reward2 values to total, because this accounts for every cheese exactly once before any reassignment.

For each cheese i, compute diff[i] = reward1[i] - reward2[i], because this is exactly the score change caused by giving that cheese to mouse one instead.

Sort diff in descending order, because the assignment must choose a fixed number of independent gains and the largest gains are the choices that maximize their sum.

Add diff[0] through diff[k - 1] to total, because these are the gains from the exactly k cheeses assigned to mouse one.

Return total, because the baseline already covers all cheeses and the selected differences replace the second-mouse rewards for precisely those k cheeses.

Complexitythe sort dominates the scan

MEASURE	BOUND	WHY
Time	O(n log n)	Building the baseline and all n differences takes linear time. Sorting the n differences takes O(n log n), and adding the first k values is O(k), which is at most O(n), so the sort dominates the total.
Space	O(n) extra	The diff array stores one value per cheese and is working memory; the scalar total and loop variables are O(1). The returned value is a single integer, so there is no output array to exclude. The extra space remains O(n) for every input shape.

Here n is the number of cheese types.

Annotated solutionC++ · sorted gains · the version to write from memory

CPPBuild the all-mouse-two baseline, sort the reassignment gains, and take exactly k of them.

#include <algorithm>
#include <vector>

using namespace std;

class Solution {
public:
    int miceAndCheese(vector<int>& reward1, vector<int>& reward2, int k) {
        int n = reward1.size();
        vector<int> diff(n);
        int total = 0;

        for (int i = 0; i < n; ++i) {
            diff[i] = reward1[i] - reward2[i];
            total += reward2[i];
        }

        sort(diff.rbegin(), diff.rend());

        for (int i = 0; i < k; ++i) {
            total += diff[i];
        }

        return total;
    }
};

The important placement is the subtraction before sorting. Sorting reward1 values alone ignores what mouse two would have earned from each cheese, while sorting reward1[i] - reward2[i] compares choices on equal footing. The loop adds exactly k differences, so even when every gain is negative, the method still obeys the required number of cheeses for mouse one.