2611. Mice and Cheese

MediumGreedyArraySortingHeap (Priority Queue)
Leetcode Link

Problem Description

The problem describes a scenario with two mice and n types of cheese. Each type of cheese has a specific point value assigned to it, which varies depending on which mouse eats it (reward1 for the first mouse and reward2 for the second mouse). The objective is to maximize the total points scored by both mice under the constraint that the first mouse must eat exactly k types of cheese, with each cheese type being consumed by only one of the mice. The inputs provided are two arrays reward1 and reward2, representing the point values for each type of cheese for each mouse, along with an integer k that specifies the number of cheese types the first mouse must eat.

The goal of the problem is to determine the maximum number of points that can be achieved by optimally distributing the cheese between the two mice.

Intuition

To arrive at the solution, we can use a greedy approach that aims to maximize the total points gained by both mice each time we decide which mouse eats a particular cheese. This means we need to make choices that will benefit our total score the most at each step.

The key insight is to look at the difference in points each mouse would gain for each type of cheese, i.e., reward1[i] - reward2[i]. If this difference is large, it means that giving the cheese to the first mouse is very advantageous compared to giving it to the second mouse, and vice versa.

By sorting the cheese in descending order of this difference, we can ensure that the first mouse eats the cheese that provides the greatest relative advantage over the second mouse. This way, when we give k types of cheese to the first mouse, we're maximizing the point difference that those k types contribute.

Once we sort the cheese accordingly, the first k pieces in this order are eaten by the first mouse, and the rest are eaten by the second mouse. This strategy ensures that the accumulated points are maximized, resulting in the highest possible score.

The given Python code implements this intuition by first sorting the cheese indices based on the point difference and calculating the total points by summing up the appropriate reward1 and reward2 values according to the sorted indices.

Learn more about Greedy, Sorting and Heap (Priority Queue) patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Which of these properties could exist for a graph but not a tree?

Solution Approach

The Python solution utilizes a greedy algorithm combined with sorting to decide the optimal distribution of cheese between the two mice. Let's walk through the algorithm step by step:

  1. Calculate the difference in score for each cheese when eaten by the first mouse compared to the second mouse. This is done by subtracting the value of reward2[i] from reward1[i] for each cheese i.

  2. Sort the indices of the cheese based on this difference in descending order. The sorting criterion, specifically lambda i: reward1[i] - reward2[i], means that the cheese types are ordered such that those with the higher score for the first mouse come first.

  3. Determine which cheese should be eaten by which mouse:

    • The first k cheeses (after sorting) will be eaten by the first mouse because they represent the cases where the first mouse gains significantly compared to the second mouse. The sum of reward1[i] for these k cheeses is calculated using sum(reward1[i] for i in idx[:k]).

    • The remaining cheeses are eaten by the second mouse. The sum of reward2[i] for the rest is calculated using sum(reward2[i] for i in idx[k:]).

  4. Add the points from step 3 to get the total maximum points.

No additional data structures are needed other than the list used for sorting the indices. The pattern used in the solution is straightforward as it revolves around the greedy choice of optimizing local decisions (which mouse should eat each cheese) to lead to a globally optimized solution (maximum points).

The overall time complexity of the algorithm is determined mainly by the sorting step, which is O(n log n), where n is the number of cheeses. The rest of the operations are linear in complexity, resulting in an efficient solution approach that scales well with the number of cheeses.

In summary, the implementation details involve creating a sorted list of indices based on the difference in points and utilizing a greedy strategy to maximize the total points by distributing the cheeses in an optimal manner.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following shows the order of node visit in a Breadth-first Search?

Example Walkthrough

Let's consider a small example to illustrate the solution approach. Suppose there are five types of cheese and the first mouse must eat exactly k=2 types of cheese. The points values are as follows:

  • For the first mouse (reward1): [5, 20, 15, 10, 25]
  • For the second mouse (reward2): [10, 30, 5, 15, 10]

Following the steps described in the solution approach:

  1. We first calculate the score difference for each cheese:
    • Cheese 1: 5 - 10 = -5
    • Cheese 2: 20 - 30 = -10
    • Cheese 3: 15 - 5 = 10
    • Cheese 4: 10 - 15 = -5
    • Cheese 5: 25 - 10 = 15

The difference array is: [-5, -10, 10, -5, 15].

  1. Next, we sort the indices of the cheeses based on the score difference in descending order:
    • Cheese 5: 15
    • Cheese 3: 10
    • Cheese 1: -5
    • Cheese 4: -5
    • Cheese 2: -10

The sorted indices are: [4, 2, 0, 3, 1].

  1. Now, we assign cheese to each mouse based on the sorted indices:

    • The first mouse eats cheeses 5 and 3 (k=2), so the points for the first mouse are: reward1[4] + reward1[2] = 25 + 15 = 40.
    • The second mouse eats the remaining cheeses (1, 4, 2), so the points for the second mouse are: reward2[0] + reward2[3] + reward2[1] = 10 + 15 + 30 = 55.

  2. The total maximum points that can be achieved by optimally distributing the cheese between the two mice is the sum of the points from step 3: 40 (first mouse) + 55 (second mouse) = 95 points.

The example demonstrates that by following the solution approach, the total points scored by both mice have been maximized through an optimal distribution of the cheese types, in accordance with their preferences.

Solution Implementation

1from typing import List
2
3class Solution:
4    def miceAndCheese(self, reward1: List[int], reward2: List[int], k: int) -> int:
5        # Determine the number of cheese pieces
6        num_cheese_pieces = len(reward1)
7
8        # Sort the indices based on the difference between rewards from reward1 and reward2
9        # Sorting in descending order since we take the largest differences first
10        sorted_indices = sorted(range(num_cheese_pieces), key=lambda i: reward1[i] - reward2[i], reverse=True)
11
12        # Calculate the total reward for the first 'k' mice using reward1
13        reward_for_first_k = sum(reward1[i] for i in sorted_indices[:k])
14
15        # Calculate the total reward for the rest of the mice using reward2
16        reward_for_remaining = sum(reward2[i] for i in sorted_indices[k:])
17
18        # Return the sum of rewards for all mice
19        return reward_for_first_k + reward_for_remaining
20
1class Solution {
2    public int miceAndCheese(int[] rewardsPath1, int[] rewardsPath2, int k) {
3        // Get the number of positions where rewards are placed
4        int positionsCount = rewardsPath1.length;
5      
6        // Create an array to store the indices of the positions
7        Integer[] positionIndices = new Integer[positionsCount];
8        for (int i = 0; i < positionsCount; ++i) {
9            positionIndices[i] = i;
10        }
11      
12        // Sort the indices based on the reward difference between the two paths
13        Arrays.sort(positionIndices, (idx1, idx2) -> rewardsPath1[idx2] - rewardsPath2[idx2] - (rewardsPath1[idx1] - rewardsPath2[idx1]));
14      
15        // Initialize the answer to start calculating the maximum reward
16        int maxReward = 0;
17      
18        // Choose the first 'k' rewards from Path 1 based on the sorted indices
19        for (int i = 0; i < k; ++i) {
20            maxReward += rewardsPath1[positionIndices[i]];
21        }
22      
23        // Choose the remaining rewards from Path 2
24        for (int i = k; i < positionsCount; ++i) {
25            maxReward += rewardsPath2[positionIndices[i]];
26        }
27      
28        // Return the total maximum reward that can be obtained
29        return maxReward;
30    }
31}
32
1class Solution {
2public:
3    int miceAndCheese(vector<int>& rewards1, vector<int>& rewards2, int k) {
4        int size = rewards1.size();  // Store the size of the rewards vectors
5
6        // Create a vector to track indices and initialize it
7        vector<int> indices(size);
8        iota(indices.begin(), indices.end(), 0);  // iota fills indices with sequential values starting with 0
9
10        // Sort the indices based on the difference in rewards between the first mouse and the second mouse
11        sort(indices.begin(), indices.end(), [&](int i, int j) {
12            // Compare differences between rewards for two indices i, j
13            return rewards1[i] - rewards2[i] > rewards1[j] - rewards2[j];
14        });
15
16        int totalReward = 0;  // Initialize the total reward accumulated
17
18        // Accumulate the maximum possible rewards by selecting k mice for rewards1 vector
19        for (int i = 0; i < k; ++i) {
20            totalReward += rewards1[indices[i]];
21        }
22
23        // Accumulate the remaining rewards by selecting mice for rewards2 vector
24        for (int i = k; i < size; ++i) {
25            totalReward += rewards2[indices[i]];
26        }
27
28        return totalReward;  // Return the total accumulated reward
29    }
30};
31
1function miceAndCheese(reward1: number[], reward2: number[], k: number): number {
2    // Determine the length of the reward arrays
3    const length = reward1.length;
4  
5    // Create an index array to keep track of the original positions
6    const indices = Array.from({ length: length }, (_, index) => index);
7  
8    // Sort the indices based on the difference between corresponding rewards
9    // The sort will prioritize the mice with higher reward difference in reward1 over reward2
10    indices.sort((indexA, indexB) => (reward1[indexB] - reward2[indexB]) - (reward1[indexA] - reward2[indexA]));
11  
12    let totalReward = 0; // Initialize total reward to 0
13
14    // Collect the top 'k' rewards from reward1 based on the sorted index positions
15    for (let i = 0; i < k; ++i) {
16        totalReward += reward1[indices[i]];
17    }
18  
19    // Collect the remaining rewards from reward2 based on the sorted index positions
20    for (let i = k; i < length; ++i) {
21        totalReward += reward2[indices[i]];
22    }
23  
24    // Return the total reward collected by the mice
25    return totalReward;
26}
27
Not Sure What to Study? Take the 2-min Quiz๏ผš

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

Time and Space Complexity

The time complexity of the given code is O(n * log n). This is because the main operation affecting the time complexity is the sorting of indexes. The sorted() function in Python uses the Timsort algorithm, which has a time complexity of O(n * log n) for the worst case. The key for the sorting operation is the difference between reward1[i] and reward2[i], but this does not change the time complexity of the sort.

The space complexity of the code is O(n). The extra space is mainly used to store the sorted indexes in the list idx. This list has the same length as the input lists (reward1 and reward2), so it takes O(n) space. The slicing operations and sum() calls do not add any additional space complexity beyond what is required for the output, and temporary variables used in the sum() function are considered O(1) space.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which data structure is used to implement recursion?

Recommended Readings

Greedy Introduction

Greedy Introduction iframe width 560 height 315 src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you

Sorting Summary

Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced

Heap Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos heap svg Priority Queue and Heap What is the relationship between priority queue and heap Priority Queue is an Abstract Data Type and Heap is the concrete data structure we use to implement a priority queue Priority Queue A priority queue

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ