2838. Maximum Coins Heroes Can Collect

Problem Description

In this battle scenario, there are n heroes and m monsters. Each hero and monster have their own power level, represented by two arrays heroes and monsters, respectively. The goal for each hero is to defeat monsters and collect coins. The number of coins that can be collected from defeating each monster is given in the array coins. The key points to note:

• A hero can defeat a monster if the hero's power is equal to or greater than the monster's power.
• After a hero defeats a monster, they earn the number of coins associated with that monster.
• Heroes remain unharmed after battles, meaning their power levels don't decrease.
• Although multiple heroes can defeat the same monster, each monster yields coins to a given hero only once.

Given this setup, we need to determine the maximum number of coins each hero can earn in total from the battle.

Intuition

The intuitive approach to solving this problem involves maximizing the coins each hero can collect. To accomplish this, we want to pair each hero with monsters they are capable of defeating and ensure we do so in a way that maximizes the total coins earned.

Here's how we approach the solution:

1. Sort the monsters by their power level while keeping track of their original indices so that we can match them with the corresponding coin values.
2. Calculate the cumulative sum of coins in the order of sorted monsters. This allows us to easily determine the total coins collected up to any point in the sorted order of monsters.
3. For each hero, find the rightmost monster in the sorted list that the hero can defeat. This step uses binary search to quickly find the position, as the sorted list allows for such a search.
4. The cumulative sum up to the position found in step 3 gives us the maximum coins a hero can earn, since all prior monsters are weaker and thus defeatable by the hero.

By applying this strategy to all heroes, we create an array of the maximum coins collected by each hero, reflecting the optimal assignment of heroes to monsters based on their power levels.

Learn more about Two Pointers, Binary Search, Prefix Sum and Sorting patterns.

Solution Approach

The solution uses a few key Python features and algorithms to achieve the goal:

1. Sorting: First, we are sorting the monsters based on their power level using the sorted() function but with an additional twist. We sort the indices of the monsters array, not the values themselves. This allows us to maintain a correlation with the coins array.

2. Cumulative Sum: We use the Python itertools.accumulate() function to compute the cumulative sum of the coins associated with each monster in increasing order of monster power. The initial=0 parameter ensures that we start with a zero value, representing that no coins are earned before defeating any monsters.

3. Binary Search: We use the bisect_right() function from Python's bisect module to perform a binary search. This function is used to find the rightmost index at which the hero's power value (h) would get inserted in the sorted monsters list to keep it in ascending order. Thus, this gives us the number of monsters that the current hero can defeat.

   • The binary search is made possible because we have sorted monsters by power, which allows us to effectively search for the largest set of monsters that a hero can defeat.

Putting it all together, the solution iterates over each hero's power and calculates the maximum coins they can collect using the precomputed cumulative sums and binary search:

• idx is the list of monster indices sorted by their power.
• s is the cumulative sum of coins in the order of the sorted monster powers.
• For each h (hero power) in heroes, the binary search finds the number of monsters that the hero can defeat, and s[i] gives the total coins earnable by defeating all monsters up to that point.
• The ans list is populated with the maximum coins for each hero and returned at the end.

By following these steps, the function efficiently matches heroes with the optimal set of monsters, ensuring that each hero earns the maximum possible coins.

Example Walkthrough

Let's use a small example to illustrate the solution approach with n heroes and m monsters. Suppose we have the following:

1heroes = [5, 10, 3]
2monsters = [4, 9, 5, 8]
3coins = [3, 5, 2, 7]

Now let's step through the solution process.

1. Sort monsters by their power level and maintain a correlation with their coin values.

1Sorted monsters (by power): [4, 5, 8, 9]
2Corresponding indices: [0, 2, 3, 1]
3
4The indices array helps us to match monsters with the original `coins` array.

2. Calculate the cumulative sum of coins based on sorted monsters’ power.

1Using original coins: [3, 5, 2, 7]
2Corresponding to sorted powers: [3, 2, 7, 5]
3Cumulative sum: [3, 5 (3+2), 12 (3+2+7), 17 (3+2+7+5)]

3. For each hero, perform a binary search to find the rightmost monster they can defeat.

1For a hero with power 5:
2Binary search will give index 1 (since the hero can defeat monsters with powers 4 and 5).
3Hence, the maximum coins this hero can earn are the cumulative sum at index 1, which is 5.
4
5For a hero with power 10:
6Binary search will give index 3 (since the hero can defeat all monsters).
7So the maximum coins this hero can earn are the cumulative sum at index 3, which is 17.
8
9For a hero with power 3:
10The hero cannot defeat any monster as the lowest monster power is 4.
11Thus, the cumulative sum for this hero is 0.

4. Compile the results into an array representing the maximum coins each hero can collect.

1For heroes' powers: [5, 10, 3]
2The maximum coins they can collect are: [5, 17, 0]

This walkthrough should now provide a clear example of how the described solution approach is applied to solve the problem. Thus, by following each of these steps, we can determine the maximum number of coins that each hero can earn from defeating monsters.

Solution Implementation

Time and Space Complexity

Time Complexity

The time complexity of the code can be broken down into the following parts:

• Sorting the index list idx: This takes O(m log m) time, where m is the length of the monsters list.
• Creating the s list with accumulated coins: The accumulate function runs in O(m) since it processes each element once.
• The for loop to fill ans list: For each hero in heroes, a binary search is performed using bisect_right, which takes O(log m). Let n be the length of the heroes list, so the loop runs in O(n log m) time.
• Combining these, the total time complexity is O(m log m + m + n log m) which simplifies to O(m log m + n log m) because the m term is dominated by the m log m term.

Space Complexity

The space complexity can be analyzed as follows:

• The idx list takes O(m) space.
• The s list also takes O(m) space.
• The ans list takes O(n) space, where n is the length of the heroes list.
• Temporary variables used inside the for loop take constant space.
• Thus, the total space complexity is O(m + n).

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