Skip to main content
Talentd

Maximum Coins Heroes Can Collect - Solution & Explanation

MediumPremiumFree on FleetCodeArrayTwo PointersBinary SearchSorting8 min readAsked at: Deutsche Bank
Practice this problem

Problem Statement

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

  • The health of a hero doesn't get reduced after defeating a monster.
  • Multiple heroes can defeat a monster, but each monster can be defeated by a given hero only once.

 

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 <= 105
  • 1 <= m == monsters.length <= 105
  • coins.length == m
  • 1 <= heroes[i], monsters[i], coins[i] <= 109

Approach Overview

Problem 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.

Solution

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force ScanO(n * m)O(1)Small input sizes or verifying logic before optimization
Sorting + Prefix Sum + Binary SearchO((n + m) log m)O(m)General optimal solution for large inputs and multiple hero queries
Sorting + Two Pointers + Prefix AccumulationO((n + m) log m)O(n)When heroes are processed in sorted order to avoid repeated binary searches

Video Solution

2838. Maximum Coins Heroes Can Collect (Leetcode Medium) • Programming Live with Larry • 306 views views

Watch 4 more video solutions →

Frequently Asked Questions

Is Maximum Coins Heroes Can Collect easy or hard?
Maximum Coins Heroes Can Collect is considered a Medium difficulty problem. The brute force idea is simple, but the optimized solution requires recognizing the preprocessing pattern with sorting, prefix sums, and binary search.
Maximum Coins Heroes Can Collect Python/Java solution
Implementations typically sort the monsters with their coin values, compute a prefix sum array, then perform a binary search for each hero. The same logic works across Python, Java, C++, Go, and TypeScript with identical complexity of O((n + m) log m).
How to solve Maximum Coins Heroes Can Collect in O(n)?
A near-linear solution can be achieved after sorting. Sort monsters by power and heroes by power (keeping original indices). Move a pointer through monsters while accumulating coins, giving each hero the current total. The scan is linear, though the initial sorting step still costs O(n log n).
What is the best approach for Maximum Coins Heroes Can Collect?
The most efficient approach uses sorting, prefix sums, and binary search. Sort monsters by power, build a prefix sum of their coins, and for each hero binary search the strongest monster they can defeat. This reduces repeated scanning and runs in O((n + m) log m) time.
Is Maximum Coins Heroes Can Collect asked at Google/Amazon/Meta?
Problems using sorting, prefix sums, and binary search patterns frequently appear in interviews at companies like Amazon, Google, and Meta. This specific style of query preprocessing and range aggregation is common in system and algorithm interviews.
What data structure is used in Maximum Coins Heroes Can Collect?
The solution primarily uses arrays along with a prefix sum array. Binary search is applied on the sorted monster powers to quickly locate the strongest monster a hero can defeat. These structures enable efficient aggregation of coin rewards.
What is the time complexity of Maximum Coins Heroes Can Collect?
The optimal solution runs in O((n + m) log m) time. Sorting the monsters takes O(m log m), and each hero query uses binary search in O(log m). Prefix sum construction is O(m), and the extra space required is O(m).

Ready to solve this problem?

Practice Maximum Coins Heroes Can Collect with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays