Problem

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 arrayans of lengthn whereans[i]_is themaximum 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.

Examples

Example 1:

1
2
3
4
5
6
7

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:

1
2
3

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:

1
2
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 <= 10^5
  • 1 <= m == monsters.length <= 10^5
  • coins.length == m
  • 1 <= heroes[i], monsters[i], coins[i] <= 10^9

Solution

Method 1 – Sorting, Prefix Sum & Binary Search

Intuition

The key idea is to efficiently determine, for each hero, the total coins from all monsters they can defeat. By sorting monsters (and their coins), we can use prefix sums and binary search to quickly compute the answer for each hero.

Approach

  1. Pair each monster’s power with its coins.
  2. Sort the monster-coin pairs by monster power.
  3. Build a prefix sum array of coins for sorted monsters.
  4. For each hero:
    • Use binary search to find the rightmost monster the hero can defeat (monster power ≤ hero power).
    • The prefix sum up to that index gives the total coins the hero can collect.
  5. Return the answer array.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    vector<long long> maximumCoins(vector<int>& heroes, vector<int>& monsters, vector<int>& coins) {
        int m = monsters.size();
        vector<pair<int, int>> mc(m);
        for (int i = 0; i < m; ++i) mc[i] = {monsters[i], coins[i]};
        sort(mc.begin(), mc.end());
        vector<long long> pre(m + 1, 0);
        for (int i = 0; i < m; ++i) pre[i + 1] = pre[i] + mc[i].second;
        vector<long long> ans;
        for (int h : heroes) {
            int l = 0, r = m;
            while (l < r) {
                int mid = (l + r) / 2;
                if (mc[mid].first <= h) l = mid + 1;
                else r = mid;
            }
            ans.push_back(pre[l]);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

func maximumCoins(heroes []int, monsters []int, coins []int) []int64 {
    m := len(monsters)
    type pair struct{ p, c int }
    mc := make([]pair, m)
    for i := 0; i < m; i++ {
        mc[i] = pair{monsters[i], coins[i]}
    }
    sort.Slice(mc, func(i, j int) bool { return mc[i].p < mc[j].p })
    pre := make([]int64, m+1)
    for i := 0; i < m; i++ {
        pre[i+1] = pre[i] + int64(mc[i].c)
    }
    ans := make([]int64, len(heroes))
    for i, h := range heroes {
        l, r := 0, m
        for l < r {
            mid := (l + r) / 2
            if mc[mid].p <= h {
                l = mid + 1
            } else {
                r = mid
            }
        }
        ans[i] = pre[l]
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    public long[] maximumCoins(int[] heroes, int[] monsters, int[] coins) {
        int m = monsters.length;
        int[][] mc = new int[m][2];
        for (int i = 0; i < m; i++) {
            mc[i][0] = monsters[i];
            mc[i][1] = coins[i];
        }
        Arrays.sort(mc, Comparator.comparingInt(a -> a[0]));
        long[] pre = new long[m + 1];
        for (int i = 0; i < m; i++) pre[i + 1] = pre[i] + mc[i][1];
        long[] ans = new long[heroes.length];
        for (int i = 0; i < heroes.length; i++) {
            int l = 0, r = m;
            while (l < r) {
                int mid = (l + r) / 2;
                if (mc[mid][0] <= heroes[i]) l = mid + 1;
                else r = mid;
            }
            ans[i] = pre[l];
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    fun maximumCoins(heroes: IntArray, monsters: IntArray, coins: IntArray): LongArray {
        val m = monsters.size
        val mc = monsters.zip(coins).sortedBy { it.first }
        val pre = LongArray(m + 1)
        for (i in 0 until m) pre[i + 1] = pre[i] + mc[i].second
        return heroes.map { h ->
            var l = 0, r = m
            while (l < r) {
                val mid = (l + r) / 2
                if (mc[mid].first <= h) l = mid + 1 else r = mid
            }
            pre[l]
        }.toLongArray()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def maximumCoins(self, heroes: list[int], monsters: list[int], coins: list[int]) -> list[int]:
        m = len(monsters)
        mc = sorted(zip(monsters, coins))
        pre = [0]
        for _, c in mc:
            pre.append(pre[-1] + c)
        ans = []
        for h in heroes:
            l, r = 0, m
            while l < r:
                mid = (l + r) // 2
                if mc[mid][0] <= h:
                    l = mid + 1
                else:
                    r = mid
            ans.append(pre[l])
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

impl Solution {
    pub fn maximum_coins(heroes: Vec<i32>, monsters: Vec<i32>, coins: Vec<i32>) -> Vec<i64> {
        let mut mc: Vec<(i32, i32)> = monsters.into_iter().zip(coins.into_iter()).collect();
        mc.sort_unstable();
        let mut pre = vec![0i64; mc.len() + 1];
        for (i, &(_, c)) in mc.iter().enumerate() {
            pre[i + 1] = pre[i] + c as i64;
        }
        heroes.into_iter().map(|h| {
            let mut l = 0;
            let mut r = mc.len();
            while l < r {
                let mid = (l + r) / 2;
                if mc[mid].0 <= h { l = mid + 1; } else { r = mid; }
            }
            pre[l]
        }).collect()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    maximumCoins(heroes: number[], monsters: number[], coins: number[]): number[] {
        const m = monsters.length;
        const mc = monsters.map((v, i) => [v, coins[i]]).sort((a, b) => a[0] - b[0]);
        const pre = [0];
        for (let i = 0; i < m; i++) pre.push(pre[pre.length - 1] + mc[i][1]);
        return heroes.map(h => {
            let l = 0, r = m;
            while (l < r) {
                const mid = (l + r) >> 1;
                if (mc[mid][0] <= h) l = mid + 1;
                else r = mid;
            }
            return pre[l];
        });
    }
}

Complexity

  • ⏰ Time complexity: O((n + m) log m), since sorting monsters is O(m log m), and for each hero (n), we do a binary search (O(log m)).
  • 🧺 Space complexity: O(m + n), for storing sorted monsters, prefix sums, and the answer array.