Skip to content

2838. Maximum Coins Heroes Can Collect 👍

  • Time: $O(\texttt{sort} + m\log n)$
  • Space: $O(m)$
 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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
 public:
  vector<long long> maximumCoins(vector<int>& heroes, vector<int>& monsters,
                                 vector<int>& coins) {
    const vector<pair<int, int>> monsterAndCoins =
        getSortedMonsterAndCoins(monsters, coins);
    vector<long long> ans;
    vector<long long> coinsPrefix{0};

    for (const auto& [_, coin] : monsterAndCoins)
      coinsPrefix.push_back(coinsPrefix.back() + coin);

    for (const int hero : heroes)
      ans.push_back(coinsPrefix[firstGreaterEqual(monsterAndCoins, hero)]);

    return ans;
  }

 private:
  vector<pair<int, int>> getSortedMonsterAndCoins(const vector<int>& monsters,
                                                  const vector<int>& coins) {
    vector<pair<int, int>> monsterAndCoins;
    for (int i = 0; i < monsters.size(); ++i)
      monsterAndCoins.emplace_back(monsters[i], coins[i]);
    ranges::sort(monsterAndCoins);
    return monsterAndCoins;
  }

  int firstGreaterEqual(const vector<pair<int, int>>& monsterAndCoins,
                        int hero) {
    int l = 0;
    int r = monsterAndCoins.size();
    while (l < r) {
      const int m = (l + r) / 2;
      if (monsterAndCoins[m].first > hero)
        r = m;
      else
        l = m + 1;
    }
    return l;
  }
};

 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
28
29
30
31
32
33
34
35
36
class Solution {
  public long[] maximumCoins(int[] heroes, int[] monsters, int[] coins) {
    Pair<Integer, Integer>[] monsterAndCoins = getSortedMonsterAndCoins(monsters, coins);
    long[] ans = new long[heroes.length];
    long[] coinsPrefix = new long[coins.length + 1];

    for (int i = 0; i < monsterAndCoins.length; ++i)
      coinsPrefix[i + 1] = coinsPrefix[i] + monsterAndCoins[i].getValue();

    for (int i = 0; i < heroes.length; ++i)
      ans[i] = coinsPrefix[firstGreaterEqual(monsterAndCoins, heroes[i])];

    return ans;
  }

  private Pair<Integer, Integer>[] getSortedMonsterAndCoins(int[] monsters, int[] coins) {
    Pair<Integer, Integer>[] monsterAndCoins = new Pair[monsters.length];
    for (int i = 0; i < monsters.length; ++i)
      monsterAndCoins[i] = new Pair<>(monsters[i], coins[i]);
    Arrays.sort(monsterAndCoins, (a, b) -> a.getKey().compareTo(b.getKey()));
    return monsterAndCoins;
  }

  private int firstGreaterEqual(Pair<Integer, Integer>[] monsterAndCoins, int hero) {
    int l = 0;
    int r = monsterAndCoins.length;
    while (l < r) {
      final int m = (l + r) / 2;
      if (monsterAndCoins[m].getKey() > hero)
        r = m;
      else
        l = m + 1;
    }
    return l;
  }
}

 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
class Solution:
  def maximumCoins(
      self,
      heroes: list[int],
      monsters: list[int],
      coins: list[int]
  ) -> list[int]:
    monsterAndCoins = sorted(list(zip(monsters, coins)))
    coinsPrefix = list(itertools.accumulate(
        (coin for _, coin in monsterAndCoins),
        initial=0))
    return [coinsPrefix[self._firstGreaterEqual(monsterAndCoins, hero)]
            for hero in heroes]

  def _firstGreaterEqual(
      self,
      monsterAndCoins: list[tuple[int, int]],
      hero: int,
  ) -> int:
    l, r = 0, len(monsterAndCoins)
    while l < r:
      m = (l + r) // 2
      if monsterAndCoins[m][0] > hero:
        r = m
      else:
        l = m + 1
    return l