Maximum Coins Heroes Can Collect

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def maximumCoins(self, heroes: List[int], monsters: List[int], coins: List[int]) -> List[int]:
        mon_cost = sorted(list(zip(monsters, coins)))
        ps = [0]
        for _, c in mon_cost: ps.append(ps[-1] + c)

        res = []
        for h in heroes:
            l, r = 0, len(monsters) - 1
            while l <= r:
                m = (l + r) // 2
                if mon_cost[m][0] > h: r = m - 1
                else: l = m + 1
            res.append(ps[l])
        return res

Explanation

The code is a Python solution to a problem where you are given three lists: heroes, monsters, and coins. The goal is to find, for each hero, the maximum number of coins you can collect by defeating monsters that the hero can beat.

Details

  1. Initialization:

    • mon_cost sorts the monsters and coins together. This way, you know how many coins each monster yields.
    • ps is a prefix sum array, where ps[i] will contain the sum of coins for defeating the first i monsters.
    • res is the list that will hold the maximum coins that each hero can collect.

  2. Calculate Prefix Sum for Monsters:

    • Loop through mon_cost and fill the ps array. It will help in quickly finding the total coins for a range of monsters.

  3. Find Maximum Coins for Each Hero:

    • For each hero h, use binary search to find the strongest monster that the hero can beat.
    • Append the maximum coins corresponding to that monster to res.

Steps

  1. Sort Monsters with Their Coin Value:

    1

    mon_cost = sorted(list(zip(monsters, coins)))
    • Zips monsters and coins and sorts them based on monster strength.

  2. Calculate Prefix Sum for Monsters’ Coins:

    1
2
3

    ps = [0]
for _, c in mon_cost: 
    ps.append(ps[-1] + c)
    • Adds up coins as you loop through sorted mon_cost, storing them in ps.

  3. Binary Search for Each Hero:

    1
2
3
4
5
6
7
8

    for h in heroes:
    l, r = 0, len(monsters) - 1
    while l <= r:
        m = (l + r) // 2
        if mon_cost[m][0] > h: 
            r = m - 1
        else: 
            l = m + 1
    • For each hero, this binary search finds the index l of the strongest monster they can defeat.

  4. Append Coins to Result:

    1

    res.append(ps[l])
    • Using index l, ps[l] gives us the maximum coins a hero can collect. We append it to res.

  5. Return Result:

    1

    return res
    • Return the res list, which contains the answer for each hero.

Key Takeaways

  • The use of sorting and prefix sum optimizes the problem.
  • Binary search helps to find the range of monsters a hero can defeat quickly.
  • Prefix sum allows for constant-time lookup to find the sum of coins a hero can collect.

This code is a good example of combining multiple techniques like sorting, prefix sum, and binary search to solve a problem efficiently.