There is a battle and n heroes are trying to defeat m monsters. You are given two 1-indexed arrays of positive integers heroes and monsters of length n and m, respectively. heroes[i] is the power of ith hero, and monsters[i] is the power of ith monster.
The ith hero can defeat the jth monster if monsters[j] <= heroes[i].
You are also given a 1-indexed array coins of length m consisting of positive integers. coins[i] is the number of coins that each hero earns after defeating the ith monster.
Return an array ans of length n where ans[i] is the maximum number of coins that the ith hero can collect from this battle.
Notes
Example 1:
Input: heroes = [1,4,2], monsters = [1,1,5,2,3], coins = [2,3,4,5,6] Output: [5,16,10] Explanation: For each hero, we list the index of all the monsters he can defeat: 1st hero: [1,2] since the power of this hero is 1 and monsters[1], monsters[2] <= 1. So this hero collects coins[1] + coins[2] = 5 coins. 2nd hero: [1,2,4,5] since the power of this hero is 4 and monsters[1], monsters[2], monsters[4], monsters[5] <= 4. So this hero collects coins[1] + coins[2] + coins[4] + coins[5] = 16 coins. 3rd hero: [1,2,4] since the power of this hero is 2 and monsters[1], monsters[2], monsters[4] <= 2. So this hero collects coins[1] + coins[2] + coins[4] = 10 coins. So the answer would be [5,16,10].
Example 2:
Input: heroes = [5], monsters = [2,3,1,2], coins = [10,6,5,2] Output: [23] Explanation: This hero can defeat all the monsters since monsters[i] <= 5. So he collects all of the coins: coins[1] + coins[2] + coins[3] + coins[4] = 23, and the answer would be [23].
Example 3:
Input: heroes = [4,4], monsters = [5,7,8], coins = [1,1,1] Output: [0,0] Explanation: In this example, no hero can defeat a monster. So the answer would be [0,0],
Constraints:
1 <= n == heroes.length <= 1051 <= m == monsters.length <= 105coins.length == m1 <= heroes[i], monsters[i], coins[i] <= 109Problem Overview: You get three arrays: heroes, monsters, and coins. Each monster has a power and a coin reward. A hero can defeat every monster whose power is less than or equal to the hero's power. For each hero, return the total coins obtainable from all monsters they can defeat.
Approach 1: Brute Force Scan (O(n * m) time, O(1) space)
For every hero, iterate through all monsters and add the coin value if the monster's power is less than or equal to the hero's power. This requires checking all m monsters for each of the n heroes. The implementation is trivial but inefficient for large inputs because the nested iteration leads to O(n * m) time complexity. No additional data structures are required, so space complexity stays O(1). This approach mainly helps confirm correctness before optimizing.
Approach 2: Sorting + Prefix Sum + Binary Search (O((n + m) log m) time, O(m) space)
The key observation: monsters can be preprocessed once. Sort monsters by power using sorting. While iterating through the sorted monsters, build a prefix sum array of coins so that prefix[i] stores the total coins from the first i monsters. Now each hero only needs to know how many monsters they can defeat.
For a hero with power h, use binary search to find the rightmost monster whose power is <= h. If the index found is k, the total coins the hero can collect equals prefix[k]. The prefix array ensures constant-time coin aggregation, which is a standard application of prefix sum optimization. Each query becomes O(log m), and preprocessing costs O(m log m).
An alternative implementation replaces binary search with a two-pointer sweep. Sort heroes while preserving original indices, then move a pointer across sorted monsters and accumulate coins as hero power increases. This produces the same result with similar asymptotic complexity and fewer binary searches.
Recommended for interviews: The sorting + prefix sum + binary search approach is what interviewers expect. It shows you recognize that repeated queries over static data should be preprocessed. Starting with the brute force demonstrates baseline reasoning, while the optimized approach proves you understand preprocessing, prefix aggregation, and logarithmic lookups.
We can sort the monsters and coins in ascending order of the monsters' combat power, and then use prefix sum to calculate the total number of coins each hero can get by defeating the first i monsters.
Next, for each hero, we can use binary search to find the strongest monster he can defeat, and then use prefix sum to calculate the total number of coins he can get.
The time complexity is O((m + n) times log n), and the space complexity is O(m). Here, m and n are the number of monsters and heroes, respectively.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Scan | O(n * m) | O(1) | Small input sizes or verifying logic before optimization |
| Sorting + Prefix Sum + Binary Search | O((n + m) log m) | O(m) | General optimal solution for large inputs and multiple hero queries |
| Sorting + Two Pointers + Prefix Accumulation | O((n + m) log m) | O(n) | When heroes are processed in sorted order to avoid repeated binary searches |
2838. Maximum Coins Heroes Can Collect (Leetcode Medium) • Programming Live with Larry • 304 views views
Watch 3 more video solutions →Practice Maximum Coins Heroes Can Collect with our built-in code editor and test cases.
Practice on FleetCode