Back to all solutions
#2838 - Maximum Coins Heroes Can Collect
Problem Description
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.
Solution
/**
* @param {number[]} heroes
* @param {number[]} monsters
* @param {number[]} coins
* @return {number[]}
*/
var maximumCoins = function(heroes, monsters, coins) {
const monsterCoinPairs = monsters.map((monster, i) => [monster, coins[i]]);
monsterCoinPairs.sort((a, b) => a[0] - b[0]);
const sortedMonsters = monsterCoinPairs.map(pair => pair[0]);
const sortedCoins = monsterCoinPairs.map(pair => pair[1]);
const prefixSum = [0];
for (let i = 0; i < sortedCoins.length; i++) {
prefixSum[i + 1] = prefixSum[i] + sortedCoins[i];
}
const result = [];
for (const heroPower of heroes) {
const defeatedCount = bisectRight(sortedMonsters, heroPower);
result.push(prefixSum[defeatedCount]);
}
return result;
function bisectRight(arr, target) {
let left = 0;
let right = arr.length;
while (left < right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] <= target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
};