Difficulty: 🟡 Medium
Topics: Array, Two Pointers, Binary Search, Sorting, Prefix Sum

Solution

LeetCode 2838 - Maximum Coins Heroes Can Collect

Problem Understanding

This problem gives us three arrays:

heroes, where heroes[i] represents the power of the ith hero.
monsters, where monsters[j] represents the power of the jth monster.
coins, where coins[j] represents the reward obtained for defeating the jth monster.

A hero can defeat every monster whose power is less than or equal to the hero's power. Defeating a monster grants the corresponding number of coins from the coins array.

An important detail is that heroes do not interfere with each other. Every hero independently fights all monsters they are capable of defeating. A monster can contribute coins to multiple heroes, because each hero's result is calculated independently.

For every hero, we must compute the total coins obtainable from all monsters satisfying:

monster_power <= hero_power

The result array should contain the maximum coin total for each hero.

The constraints are large:

n <= 100,000
m <= 100,000

A solution that compares every hero against every monster would require up to:

100,000 × 100,000 = 10^10

operations, which is far too slow.

The values of powers and coins can be as large as 10^9, but only comparisons and additions are needed. The large value range suggests that counting sort or frequency arrays are not practical.

Some important edge cases include:

A hero cannot defeat any monster.
A hero can defeat every monster.
Multiple monsters can have the same power.
Multiple heroes can have the same power.
Coin values can be very large, so the total sum may exceed 32-bit integer limits.
Heroes may appear in arbitrary order, so answers must be returned in the original order.

Approaches

Brute Force

The most direct approach is to process each hero independently.

For every hero, iterate through all monsters. Whenever a monster's power is less than or equal to the hero's power, add its coin reward to the hero's total.

This approach is correct because it explicitly checks every valid hero-monster relationship and sums exactly the rewards that the hero can collect.

However, the time complexity is:

O(n × m)

With both arrays having size up to 100,000, this becomes 10^10 operations, which is not feasible.

Key Insight

The condition for defeating a monster depends only on comparing powers:

monster_power <= hero_power

Suppose we sort all monsters by power.

For a given hero power H, every defeatable monster will appear in a contiguous prefix of the sorted monster list. Once we encounter a monster whose power exceeds H, all later monsters will also exceed H.

This transforms the problem into:

Sort monsters by power.
Build prefix sums of their coin rewards.
For each hero, find how many sorted monsters have power less than or equal to the hero's power.
Use the prefix sum array to instantly obtain the total reward.

Finding the cutoff position can be done efficiently using binary search.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(nm)	O(1)	Check every hero against every monster
Optimal	O(m log m + n log m)	O(m)	Sort monsters, build prefix sums, binary search for each hero

Algorithm Walkthrough

Optimal Algorithm

Combine each monster's power and coin reward into a pair.

This preserves the relationship between a monster and its reward after sorting. 2. Sort all monster pairs by monster power.

After sorting, monsters with lower power appear first. 3. Build a separate array containing only the sorted monster powers.

This array will be used for binary search. 4. Build a prefix sum array of coin rewards.

Let prefix[i] represent the total coins obtainable from the first i + 1 sorted monsters. 5. Process each hero independently.

For a hero with power H, perform a binary search to find the first monster whose power is greater than H. 6. Let that position be idx.

Then all monsters in positions:

[0, idx - 1]

are defeatable. 7. If idx == 0, the hero cannot defeat any monster and earns 0.

Otherwise, the hero earns:

prefix[idx - 1]

Store the result in the answer array.
Return the completed answer array.

Why it works

After sorting, all monsters with power less than or equal to a hero's power form a prefix of the sorted list. Binary search finds the size of this prefix in logarithmic time. The prefix sum array stores the total coin reward for every possible prefix. Therefore, for each hero, the algorithm exactly sums the rewards of all defeatable monsters and excludes all stronger monsters. Since every hero is processed independently, the resulting array is correct.

Python Solution

from bisect import bisect_right
from typing import List

class Solution:
    def maximumCoins(self, heroes: List[int], monsters: List[int], coins: List[int]) -> List[int]:
        monster_data = sorted(zip(monsters, coins))

        sorted_powers = [power for power, _ in monster_data]

        prefix = []
        running_sum = 0

        for _, coin in monster_data:
            running_sum += coin
            prefix.append(running_sum)

        answer = []

        for hero_power in heroes:
            idx = bisect_right(sorted_powers, hero_power)

            if idx == 0:
                answer.append(0)
            else:
                answer.append(prefix[idx - 1])

        return answer

Implementation Explanation

The first step is creating monster_data, which stores (monster_power, coin_reward) pairs. Sorting this list by power allows us to group all monsters that a hero can defeat into a prefix.

The sorted_powers array is extracted solely for binary search operations. Using Python's bisect_right, we can efficiently find how many monsters have power less than or equal to a hero's power.

Next, we build a prefix sum array. Each position stores the total reward obtainable from all monsters up to that position in the sorted order.

For every hero, bisect_right returns the insertion position immediately after the last monster whose power is less than or equal to the hero's power. This value directly tells us how many monsters are defeatable.

If no monster can be defeated, the answer is 0. Otherwise, the reward equals the prefix sum at idx - 1.

Go Solution

package main

import "sort"

func maximumCoins(heroes []int, monsters []int, coins []int) []int64 {
	type Pair struct {
		power int
		coin  int
	}

	m := len(monsters)

	monsterData := make([]Pair, m)

	for i := 0; i < m; i++ {
		monsterData[i] = Pair{
			power: monsters[i],
			coin:  coins[i],
		}
	}

	sort.Slice(monsterData, func(i, j int) bool {
		return monsterData[i].power < monsterData[j].power
	})

	powers := make([]int, m)
	prefix := make([]int64, m)

	var runningSum int64

	for i := 0; i < m; i++ {
		powers[i] = monsterData[i].power
		runningSum += int64(monsterData[i].coin)
		prefix[i] = runningSum
	}

	ans := make([]int64, len(heroes))

	for i, heroPower := range heroes {
		idx := sort.Search(len(powers), func(j int) bool {
			return powers[j] > heroPower
		})

		if idx > 0 {
			ans[i] = prefix[idx-1]
		}
	}

	return ans
}

Go-Specific Notes

The total number of coins can become very large. Since there can be up to 100,000 monsters and each coin value can be up to 10^9, the maximum sum can reach:

10^14

which exceeds 32-bit integer limits. Therefore, the Go solution uses int64 for prefix sums and the answer array.

The binary search is implemented using sort.Search, which finds the first position where the condition becomes true. Here, it finds the first monster power greater than the hero's power.

Worked Examples

Example 1

Input:

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

After pairing and sorting:

Power	Coins
1	2
1	3
2	5
3	6
5	4

Prefix sums:

Index	Prefix Sum
0	2
1	5
2	10
3	16
4	20

Hero Power = 1

bisect_right([1,1,2,3,5], 1) = 2

Result:

prefix[1] = 5

Hero Power = 4

bisect_right([1,1,2,3,5], 4) = 4

Result:

prefix[3] = 16

Hero Power = 2

bisect_right([1,1,2,3,5], 2) = 3

Result:

prefix[2] = 10

Final answer:

[5,16,10]

Example 2

Input:

heroes   = [5]
monsters = [2,3,1,2]
coins    = [10,6,5,2]

Sorted monsters:

Power	Coins
1	5
2	10
2	2
3	6

Prefix sums:

Index	Prefix Sum
0	5
1	15
2	17
3	23

Binary search:

bisect_right([1,2,2,3], 5) = 4

Result:

prefix[3] = 23

Final answer:

[23]

Example 3

Input:

heroes   = [4,4]
monsters = [5,7,8]
coins    = [1,1,1]

Sorted monsters:

Power	Coins
5	1
7	1
8	1

Binary search for each hero:

bisect_right([5,7,8], 4) = 0

No monsters can be defeated.

Final answer:

[0,0]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m log m + n log m)	Sorting monsters takes O(m log m), each hero performs a binary search in O(log m)
Space	O(m)	Sorted monster data, power array, and prefix sums

The dominant preprocessing step is sorting the monsters. After that, every hero can be answered independently in logarithmic time through binary search. This is efficient enough for the maximum constraint size of 100,000.

Test Cases

from typing import List

s = Solution()

assert s.maximumCoins(
    [1, 4, 2],
    [1, 1, 5, 2, 3],
    [2, 3, 4, 5, 6]
) == [5, 16, 10]  # Example 1

assert s.maximumCoins(
    [5],
    [2, 3, 1, 2],
    [10, 6, 5, 2]
) == [23]  # Example 2

assert s.maximumCoins(
    [4, 4],
    [5, 7, 8],
    [1, 1, 1]
) == [0, 0]  # Example 3

assert s.maximumCoins(
    [1],
    [1],
    [10]
) == [10]  # Single hero and monster

assert s.maximumCoins(
    [1],
    [2],
    [10]
) == [0]  # Hero cannot defeat monster

assert s.maximumCoins(
    [10],
    [1, 2, 3, 4],
    [5, 5, 5, 5]
) == [20]  # Hero defeats all monsters

assert s.maximumCoins(
    [3, 3, 3],
    [1, 2, 3],
    [10, 20, 30]
) == [60, 60, 60]  # Duplicate hero powers

assert s.maximumCoins(
    [2],
    [2, 2, 2],
    [1, 2, 3]
) == [6]  # Duplicate monster powers

assert s.maximumCoins(
    [1000000000],
    [1000000000],
    [1000000000]
) == [1000000000]  # Maximum value inputs

assert s.maximumCoins(
    [5],
    [1, 2, 3, 4, 5],
    [100, 200, 300, 400, 500]
) == [1500]  # Large cumulative sum

Test Summary

Test	Why
Example 1	Validates mixed powers and partial monster coverage
Example 2	Validates defeating all monsters
Example 3	Validates defeating no monsters
Single hero and monster	Smallest nontrivial input
Hero weaker than monster	Zero reward case
Hero defeats all monsters	Full prefix selected
Duplicate hero powers	Same answer should repeat
Duplicate monster powers	Binary search boundary correctness
Maximum value inputs	Large power values
Large cumulative sum	Validates reward accumulation

Edge Cases

No Defeatable Monsters

A hero may have power smaller than every monster. In this situation, binary search returns position 0, meaning there are no monsters in the valid prefix. A common bug is attempting to access prefix[-1]. The implementation explicitly checks for idx == 0 and returns 0.

Multiple Monsters With Equal Power

Several monsters may have exactly the same power. The problem requires that all monsters whose power is less than or equal to the hero's power contribute rewards. Using bisect_right rather than bisect_left ensures that all equal-power monsters are included in the count.

Very Large Coin Totals

Each coin value can be as large as 10^9, and there can be 100,000 monsters. The total reward can therefore reach 10^14. Using 32-bit integers would overflow. The Go implementation stores prefix sums and answers in int64, ensuring correctness for the maximum possible input size.

Heroes Appearing in Arbitrary Order

Heroes are not sorted and answers must be returned in the same order as the input. The algorithm processes each hero independently and appends results directly to the answer array, preserving the original ordering automatically.

All Monsters Having Greater Power Than Heroes

When every monster is stronger than every hero, every binary search returns 0. The algorithm naturally produces an answer array filled with zeros, which matches the problem requirements.