Maximum coins heroes can collect

Array Two Pointers Binary Search Sorting Prefix Sum

68.7% acceptance

Mar 31, 2026

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

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn maximum_coins(heroes: Vec<i32>, monsters: Vec<i32>, coins: Vec<i32>) -> Vec<i64> {
    let mut pairs: Vec<(i32, i32)> = monsters.into_iter().zip(coins.into_iter()).collect();
    pairs.sort();
    let m = pairs.len();
    let mut prefix = vec![0i64; m + 1];
    for i in 0..m {
      prefix[i + 1] = prefix[i] + pairs[i].1 as i64;
    }
    heroes.iter().map(|&h| {
      let idx = pairs.partition_point(|&(mon, _)| mon <= h);
      prefix[idx]
    }).collect()
  }
}