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.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

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.
  1. 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)]
  1. 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.
  1. 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

1from itertools import accumulate
2from bisect import bisect_right
3from typing import List
4
5class Solution:
6    def maximumCoins(self, heroes: List[int], monsters: List[int], coins: List[int]) -> List[int]:
7        # Define the number of monsters
8        num_monsters = len(monsters)
9
10        # Create sorted indices of the monsters based on their strength
11        # The weakest monsters come first in the list
12        sorted_indices = sorted(range(num_monsters), key=lambda i: monsters[i])
13      
14        # Calculate the cumulative sum of coins based on the sorted indices
15        # 's' will contain the cumulative coins we get after defeating monsters in sorted order
16        # The 'initial=0' argument ensures that there is a 0 at the beginning of the list
17        cumulative_coins = list(accumulate((coins[i] for i in sorted_indices), initial=0))
18      
19        # Initialize a list to store the maximum coins that can be collected by each hero
20        collected_coins = []
21
22        # Iterate over each hero
23        for hero_strength in heroes:
24            # Find the furthest right position in the sorted monster list that the hero can defeat
25            # bisect_right returns the index where to insert hero_strength to keep the list sorted
26            monster_position = bisect_right(sorted_indices, hero_strength, key=lambda i: monsters[i])
27          
28            # Append the cumulative coins up to that monster position for current hero's strength
29            collected_coins.append(cumulative_coins[monster_position])
30      
31        # Return the list containing the maximum coins that each hero can collect
32        return collected_coins
33
1class Solution {
2    public long[] maximumCoins(int[] heroes, int[] monsters, int[] coins) {
3        int monsterCount = monsters.length;
4        Integer[] sortedIndices = new Integer[monsterCount];
5        // Initialize sortedIndices with array indices
6        for (int i = 0; i < monsterCount; ++i) {
7            sortedIndices[i] = i;
8        }
9
10        // Sort the indices based on the monsters' strength
11        Arrays.sort(sortedIndices, Comparator.comparingInt(j -> monsters[j]));
12
13        // Create a prefix sum array for coins based on sorted indices of monsters
14        long[] prefixSums = new long[monsterCount + 1];
15        for (int i = 0; i < monsterCount; ++i) {
16            prefixSums[i + 1] = prefixSums[i] + coins[sortedIndices[i]];
17        }
18
19        int heroCount = heroes.length;
20        long[] answer = new long[heroCount];
21      
22        // For each hero, find their maximum possible collectable coins
23        for (int k = 0; k < heroCount; ++k) {
24            // Find the number of monsters a hero can defeat
25            int monsterDefeated = search(monsters, sortedIndices, heroes[k]);
26            // Assign the sum of coins from the monsters a hero can defeat
27            answer[k] = prefixSums[monsterDefeated];
28        }
29
30        return answer;
31    }
32  
33    // Binary search to find the number of monsters a hero can defeat
34    private int search(int[] nums, Integer[] indices, int heroStrength) {
35        int left = 0, right = indices.length;
36        while (left < right) {
37            int mid = (left + right) >> 1;
38            // Check if the mid-point monster is stronger than the hero
39            if (nums[indices[mid]] > heroStrength) {
40                right = mid; // Look in the left subarray
41            } else {
42                left = mid + 1; // Look in the right subarray
43            }
44        }
45        // left now points to the number of monsters the hero can defeat
46        return left;
47    }
48}
49
1#include <vector>
2#include <numeric>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9    vector<long long> maximumCoins(vector<int>& heroes, vector<int>& monsters, vector<int>& coins) {
10        // The number of monsters, used for setting up various bounds and loops
11        int monsterCount = monsters.size();
12
13        // Create a vector of indices corresponding to monster array positions
14        vector<int> monsterIndices(monsterCount);
15        iota(monsterIndices.begin(), monsterIndices.end(), 0);
16
17        // Sort the indices based on the monster strengths (from the monsters array),
18        // so we can later find out how many monsters a hero can defeat
19        sort(monsterIndices.begin(), monsterIndices.end(), [&](int i, int j) {
20            return monsters[i] < monsters[j];
21        });
22
23        // Prefix sum array to quickly calculate total coins up to a certain monster
24        long long prefixSum[monsterCount + 1];
25        prefixSum[0] = 0;
26        for (int i = 1; i <= monsterCount; ++i) {
27            prefixSum[i] = prefixSum[i - 1] + coins[monsterIndices[i - 1]];
28        }
29
30        // The answer vector to store maximum coins for each hero
31        vector<long long> answer;
32
33        // A lambda to search for the right-most position where a hero can defeat monsters
34        auto search = [&](int strength) {
35            int left = 0, right = monsterCount;
36            while (left < right) {
37                int mid = (left + right) >> 1;
38                if (monsters[monsterIndices[mid]] > strength) {
39                    right = mid;
40                } else {
41                    left = mid + 1;
42                }
43            }
44            return left;
45        };
46
47        // Use the search function defined above to calculate the total coins each hero can collect
48        for (int heroStrength : heroes) {
49            answer.push_back(prefixSum[search(heroStrength)]);
50        }
51
52        return answer;
53    }
54};
55
56// Note: Although this code compiles and adheres to standard C++ syntax, without additional context it is unclear what this algorithm is intended to solve.
57// It seems to match heroes against a sorted list of monsters by their strength and calculate the maximum coins each hero can collect based on the monsters they can defeat.
58
1function maximumCoins(heroes: number[], monsters: number[], coins: number[]): number[] {
2    // Length of the monsters array
3    const numberOfMonsters = monsters.length;
4
5    // Create an index array from 0 to numberOfMonsters-1
6    const indices: number[] = Array.from({ length: numberOfMonsters }, (_, i) => i);
7
8    // Sort the indices array based on the corresponding value in the monsters array
9    indices.sort((a, b) => monsters[a] - monsters[b]);
10
11    // 'prefixSum' represents cumulative coins amount from monsters sorted on strength
12    const prefixSum: number[] = Array(numberOfMonsters + 1).fill(0);
13    for (let i = 0; i < numberOfMonsters; ++i) {
14        prefixSum[i + 1] = prefixSum[i] + coins[indices[i]];
15    }
16
17    // Binary search helper method that finds how many monsters a hero can defeat
18    const searchMonsters = (strength: number): number => {
19        let low = 0;
20        let high = numberOfMonsters;
21
22        // Look for the rightmost monster that hero can defeat
23        while (low < high) {
24            const mid = (low + high) >> 1; // Equivalent to Math.floor((low + high) / 2)
25            if (monsters[indices[mid]] > strength) {
26                high = mid;
27            } else {
28                low = mid + 1;
29            }
30        }
31        return low;
32    };
33
34    // Map heroes to their maximum coins earnings based on which monsters they can defeat
35    return heroes.map(heroStrength => prefixSum[searchMonsters(heroStrength)]);
36}
37

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.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

What's the relationship between a tree and a graph?


Recommended Readings