Problem Description

In this problem, there's a battle scenario where n heroes are fighting against m monsters. Each hero and monster has a power level, and heroes can defeat monsters based on their relative power.

You're given three arrays:

• heroes[i] represents the power of the i-th hero (1-indexed, length n)
• monsters[i] represents the power of the i-th monster (1-indexed, length m)
• coins[i] represents the reward for defeating the i-th monster (1-indexed, length m)

Battle Rules:

• A hero with power heroes[i] can defeat a monster with power monsters[j] if and only if monsters[j] <= heroes[i]
• When any hero defeats a monster, they earn the corresponding coins for that monster
• Each hero can defeat multiple monsters (their health doesn't decrease)
• Multiple heroes can defeat the same monster and each earn the reward
• However, each individual hero can only defeat each monster once (no repeated rewards from the same monster)

Goal: For each hero, determine the maximum number of coins they can collect by defeating all monsters they're capable of defeating.

The output should be an array ans of length n where ans[i] contains the maximum coins the i-th hero can collect.

Example Logic: If a hero has power 5, they can defeat all monsters with power ≤ 5. The hero would collect coins from all these defeatable monsters, and the sum of those coins would be their maximum earnings.

Intuition

The key insight is that each hero wants to defeat all monsters they're capable of defeating to maximize their coin collection. Since a hero with power h can defeat any monster with power ≤ h, we need to efficiently find all such monsters for each hero.

If we think about this problem naively, for each hero, we'd check every monster to see if they can defeat it, then sum up the coins. This would take O(n * m) time, which could be inefficient for large inputs.

A smarter approach emerges when we realize that if we sort the monsters by their power, then for a hero with power h, they can defeat all monsters up to a certain position in the sorted array. All monsters before this position have power ≤ h, and all monsters after have power > h.

This observation leads us to think about:

1. Sorting monsters by power - This creates a clear cutoff point for each hero
2. Using prefix sums - Since a hero collects coins from all defeatable monsters (a contiguous range from the start of the sorted array), we can precompute cumulative sums of coins
3. Binary search - To quickly find the cutoff point (the strongest monster a hero can defeat) in the sorted array

The workflow becomes:

• Sort monsters and their corresponding coins together by monster power
• Build a prefix sum array where prefix[i] = total coins from defeating the first i monsters in sorted order
• For each hero, binary search to find the last monster they can defeat
• The prefix sum at that position gives the total coins that hero can collect

This reduces our time complexity from O(n * m) to O(m log m + n log m), making it much more efficient.

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

Solution Approach

Let's walk through the implementation step by step:

Step 1: Sort monsters while preserving original indices

Since we need to match coins with their corresponding monsters after sorting, we create an index array and sort it based on monster powers:

idx = sorted(range(m), key=lambda i: monsters[i])

This gives us the indices of monsters in ascending order of their power. For example, if monsters = [2, 5, 1], then idx = [2, 0, 1] (monster at index 2 has power 1, at index 0 has power 2, at index 1 has power 5).

Step 2: Build prefix sum array for coins

Using the sorted order, we calculate cumulative coin sums:

s = list(accumulate((coins[i] for i in idx), initial=0))

The accumulate function with initial=0 creates a prefix sum where:

• s[0] = 0 (no monsters defeated)
• s[1] = coins[idx[0]] (coins from defeating the weakest monster)
• s[2] = coins[idx[0]] + coins[idx[1]] (coins from defeating the 2 weakest monsters)
• And so on...

Step 3: Process each hero using binary search

For each hero with power h, we find the strongest monster they can defeat:

for h in heroes:
    i = bisect_right(idx, h, key=lambda i: monsters[i])
    ans.append(s[i])

The bisect_right function with the custom key finds the rightmost position where we can insert h while maintaining sorted order. This effectively tells us how many monsters have power ≤ h.

• The key=lambda i: monsters[i] ensures we're comparing hero power h with monster powers
• bisect_right returns the count of monsters that can be defeated (since it finds the position after the last defeatable monster)
• s[i] gives us the total coins from defeating those i monsters

Example walkthrough:

If monsters = [1, 3, 5], coins = [2, 4, 6], and heroes = [2, 4, 6]:

1. After sorting: monsters stay in order, idx = [0, 1, 2]
2. Prefix sums: s = [0, 2, 6, 12]
3. For hero with power 2: bisect_right finds 1 monster (power 1), returns coins = s[1] = 2
4. For hero with power 4: bisect_right finds 2 monsters (powers 1, 3), returns coins = s[2] = 6
5. For hero with power 6: bisect_right finds 3 monsters (all), returns coins = s[3] = 12

The time complexity is O(m log m) for sorting plus O(n log m) for processing all heroes with binary search, giving us O(m log m + n log m) overall.

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Given:

• heroes = [4, 2] (2 heroes with powers 4 and 2)
• monsters = [1, 3, 5, 2] (4 monsters with these power levels)
• coins = [10, 20, 30, 15] (rewards for defeating each monster)

Step 1: Sort monsters by power while preserving coin associations

We create an index array and sort it based on monster powers:

• Original indices: [0, 1, 2, 3]
• Monster powers: [1, 3, 5, 2]
• Sorted indices by monster power: idx = [0, 3, 1, 2]
  • This means: monster 0 (power 1), monster 3 (power 2), monster 1 (power 3), monster 2 (power 5)

Step 2: Build prefix sum array for coins in sorted order

Following the sorted order, we accumulate coins:

• Coins in sorted order: [10, 15, 20, 30] (corresponding to monsters with powers 1, 2, 3, 5)
• Prefix sum array: s = [0, 10, 25, 45, 75]
  • s[0] = 0 (no monsters defeated)
  • s[1] = 10 (defeat monster with power 1)
  • s[2] = 25 (defeat monsters with powers 1 and 2)
  • s[3] = 45 (defeat monsters with powers 1, 2, and 3)
  • s[4] = 75 (defeat all monsters)

Step 3: Process each hero using binary search

For Hero 1 (power = 4):

• We need to find how many monsters have power ≤ 4
• Binary search in sorted monster powers [1, 2, 3, 5] for position where 4 would fit
• bisect_right returns index 3 (can defeat first 3 monsters: powers 1, 2, 3)
• Total coins = s[3] = 45

For Hero 2 (power = 2):

• We need to find how many monsters have power ≤ 2
• Binary search in sorted monster powers [1, 2, 3, 5] for position where 2 would fit
• bisect_right returns index 2 (can defeat first 2 monsters: powers 1, 2)
• Total coins = s[2] = 25

Final Answer: [45, 25]

This approach efficiently finds the maximum coins each hero can collect by:

1. Sorting monsters once (O(m log m))
2. Using prefix sums to avoid recalculating coin totals
3. Using binary search for each hero to quickly find their defeatable monsters (O(log m) per hero)

The total complexity is O(m log m + n log m), much better than the naive O(n × m) approach of checking every hero-monster pair.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m log m + n log m) where m is the number of monsters and n is the number of heroes.

• Sorting the indices based on monster values: O(m log m)
• Creating the prefix sum array using accumulate: O(m)
• For each hero in the heroes list (n iterations):
  • bisect_right performs binary search on the sorted indices: O(log m)
  • Total for all heroes: O(n log m)
• Overall: O(m log m + m + n log m) = O(m log m + n log m)

Note: The reference answer states O((m + n) × log n), but this appears to be incorrect. The sorting is done on monsters (size m), and binary search is performed on the sorted monster indices (also size m), not on heroes (size n).

Space Complexity: O(m) where m is the number of monsters.

• idx array storing sorted indices: O(m)
• s prefix sum array: O(m + 1) = O(m)
• ans array storing results: O(n), but this is typically not counted as it's the output
• Overall auxiliary space: O(m)

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

Common Pitfalls

1. Incorrect Handling of Duplicate Monster Powers

The Pitfall: When multiple monsters have the same power level, developers might incorrectly assume that bisect_right will handle them properly without considering the sorting stability. If not careful with the implementation, you might accidentally use bisect_left instead of bisect_right, which would exclude monsters with power exactly equal to the hero's power.

Example of the issue:

# WRONG: Using bisect_left would miss monsters with power equal to hero's power
num_defeatable = bisect_left(sorted_indices, hero_power, key=lambda i: monsters[i])

If monsters = [2, 3, 3, 4] and hero power is 3, bisect_left would return index 1 (only defeating the monster with power 2), while bisect_right correctly returns index 3 (defeating monsters with powers 2, 3, and 3).

Solution: Always use bisect_right to ensure all monsters with power equal to the hero's power are included in the count.

2. Memory Inefficiency with Large Inputs

The Pitfall: Creating the prefix sum array using list(accumulate(...)) materializes the entire list in memory. For very large inputs, this could cause memory issues, especially if you're also storing intermediate results.

Example of inefficient approach:

# Creates unnecessary intermediate list
coins_sorted = [coins[i] for i in sorted_indices]
prefix_sums = [0]
for coin in coins_sorted:
    prefix_sums.append(prefix_sums[-1] + coin)

Solution: The current implementation using accumulate with a generator expression is already memory-efficient, but ensure you're not creating unnecessary intermediate lists. The generator (coins[i] for i in sorted_indices) avoids creating a full sorted coins list.

3. Confusion Between Index and Value in Binary Search

The Pitfall: The most common mistake is confusing what bisect_right returns when using a custom key. Developers might think they're searching for an index in the original arrays, but they're actually searching within the sorted indices array.

Incorrect mental model:

# WRONG: Thinking bisect_right returns a monster index
monster_index = bisect_right(sorted_indices, hero_power, key=lambda i: monsters[i])
defeated_monster_power = monsters[monster_index]  # This would cause an IndexError!

Solution: Remember that bisect_right returns a count (position in the sorted array), not an index into the original arrays. This count directly corresponds to how many monsters can be defeated, which is why we use it to index into the prefix sum array:

num_defeatable = bisect_right(sorted_indices, hero_power, key=lambda i: monsters[i])
total_coins = prefix_sums[num_defeatable]  # Correct usage

4. Off-by-One Errors with Prefix Sums

The Pitfall: Forgetting to include initial=0 in the accumulate function or incorrectly indexing the prefix sum array can lead to off-by-one errors.

Wrong implementation:

# WRONG: No initial=0
prefix_sums = list(accumulate(coins[i] for i in sorted_indices))
# Now prefix_sums[0] is coins of first monster, not 0
# This would cause incorrect results when hero can't defeat any monsters

Solution: Always include initial=0 to ensure prefix_sums[0] = 0 represents the case where no monsters are defeated. This makes indexing intuitive: prefix_sums[k] represents the total coins from defeating exactly k monsters.