We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Coins Heroes Can Collect

Number: 3101

Difficulty: Medium

Paid? Yes

Companies: Deutsche Bank

Problem Description

Given two 1-indexed arrays, heroes and monsters, where heroes[i] represents the power of the iᵗʰ hero and monsters[j] represents the power of the jᵗʰ monster, a hero can defeat a monster if monster[j] ≤ hero[i]. Furthermore, there is a coins array (also 1-indexed) where coins[j] represents the coins earned when a hero defeats the jᵗʰ monster. Each hero can defeat each monster at most once (and defeating a monster does not decrease the hero’s power). Return an array ans of length n, where ans[i] is the maximum number of coins the iᵗʰ hero can collect in the battle.

Key Insights

  • Sort the monsters (along with their coin rewards) by the monster's power.
  • Build a prefix sum array over the coin values in the sorted order so that the total coins obtainable by defeating all monsters up to a certain power can be quickly computed.
  • For each hero, use binary search to find the count of monsters that can be defeated (i.e., monsters with power ≤ hero's power) and then use the prefix sum array to compute the total coins.
  • The approach effectively leverages sorting and binary search for an efficient solution.

Space and Time Complexity

Time Complexity: O(m log m + n log m), where m is the number of monsters and n is the number of heroes. Space Complexity: O(m) for the prefix sum and sorted monsters array.

Solution

The solution involves first pairing each monster's power with its respective coin reward and sorting these pairs by the monster's power. Then, we build a prefix sum array from the sorted coin rewards so that for any given hero, we can quickly determine the total coins obtainable by summing coins up to the largest monster power that the hero can defeat. For each hero, binary search is utilized on the sorted monster powers to determine the eligible monsters; the prefix sum array gives the cumulative coins earned. This method efficiently handles the large input constraints.

Code Solutions

# Python solution using sorting, prefix sum, and binary search.
import bisect

def max_coins(heroes, monsters, coins):
    # Pair monsters with coins and sort based on monster power.
    monster_coin_pairs = sorted(zip(monsters, coins))
    sorted_monsters = [power for power, _ in monster_coin_pairs]
    
    # Build prefix sum of coins.
    prefix_sum = []
    current_sum = 0
    for power, coin in monster_coin_pairs:
        current_sum += coin
        prefix_sum.append(current_sum)
    
    result = []
    # For each hero, find the rightmost monster the hero can defeat using binary search.
    for hero in heroes:
        # bisect_right returns the insertion index; subtract 1 to get last valid index.
        index = bisect.bisect_right(sorted_monsters, hero) - 1
        # If at least one monster is defeatable, add the cumulative coins. Otherwise, add 0.
        if index >= 0:
            result.append(prefix_sum[index])
        else:
            result.append(0)
    return result

# Example usage:
heroes = [1,4,2]
monsters = [1,1,5,2,3]
coins = [2,3,4,5,6]
print(max_coins(heroes, monsters, coins))  # Expected output: [5, 16, 10]
← Back to All Questions