Maximum Coins Heroes Can Collect - Practice Coding Problems

Maximum Coins Heroes Can Collect - Problem

Array Two Pointers Binary Search Sorting Prefix Sum Medium

There is a battle where 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 the i-th hero, and monsters[i] is the power of the i-th monster. The i-th hero can defeat the j-th 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 i-th monster.

Return an array ans of length n where ans[i] is the maximum number of coins that the i-th hero can collect from this battle.

Note: 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.

Input & Output

Example 1 — Basic Battle

$ Input: heroes = [1,4,2], monsters = [1,2,3,4], coins = [5,10,15,20]

› Output: [5,50,20]

💡 Note: Hero 1 (power 1): defeats monster 1 (power 1) → 5 coins. Hero 2 (power 4): defeats all monsters → 5+10+15+20 = 50 coins. Hero 3 (power 2): defeats monsters 1,2 → 5+10 = 15 coins.

Example 2 — No Defeats

$ Input: heroes = [1,1], monsters = [2,3], coins = [10,20]

› Output: [0,0]

💡 Note: Both heroes have power 1, but all monsters have power ≥ 2, so no defeats possible.

Example 3 — All Powerful Hero

$ Input: heroes = [10], monsters = [1,2,3], coins = [5,10,15]

› Output: [30]

💡 Note: Hero with power 10 can defeat all monsters (1,2,3) and collect 5+10+15 = 30 coins.

Constraints

1 ≤ heroes.length, monsters.length ≤ 10⁵
1 ≤ heroes[i], monsters[i] ≤ 10⁸
1 ≤ coins[i] ≤ 10⁸

Visualization

Tap to expand

Understanding the Visualization

Input

Heroes [1,4,2], Monsters [1,2,3,4], Coins [5,10,15,20]

Process

Each hero defeats monsters with power ≤ their own power

Output

Total coins each hero collects: [5,50,20]

Key Takeaway

🎯 Key Insight: Sort monsters by power, then use binary search to efficiently find how many each hero can defeat

Asked in

a Amazon 25 G Google 18 M Microsoft 15

The key insight is that stronger heroes can defeat all monsters that weaker heroes can defeat. By sorting monsters by power and using binary search with prefix sums, we can efficiently find how many coins each hero collects. Best approach is Sort + Binary Search. Time: O(m log m + n log m), Space: O(m)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n × m)	O(1)	For each hero, check all monsters and sum coins from defeatable ones
Sort and Binary Search	O(m log m + n log m)	O(m)	Sort monsters by power, then use binary search to find how many each hero can defeat

Brute Force — Algorithm Steps

For each hero, initialize total coins to 0
Check every monster to see if hero can defeat it
Sum coins from all defeatable monsters

Visualization

Tap to expand

Step-by-Step Walkthrough

Hero Selection

Pick first hero with power 3

Monster Check

Check all monsters: can defeat monsters with power ≤ 3

Sum Coins

Add up coins from all defeatable monsters

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void parseArray(char* line, int* arr, int* size) {
    *size = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        arr[(*size)++] = atoi(token);
        token = strtok(NULL, ",]");
    }
}

void solution(int* heroes, int heroesSize, int* monsters, int monstersSize, int* coins, int* result) {
    for (int i = 0; i < heroesSize; i++) {
        int totalCoins = 0;
        for (int j = 0; j < monstersSize; j++) {
            if (heroes[i] >= monsters[j]) {
                totalCoins += coins[j];
            }
        }
        result[i] = totalCoins;
    }
}

int main() {
    char line[10000];
    int heroes[1000], monsters[1000], coins[1000], result[1000];
    int heroesSize, monstersSize, coinsSize;
    
    fgets(line, sizeof(line), stdin);
    parseArray(line, heroes, &heroesSize);
    
    fgets(line, sizeof(line), stdin);
    parseArray(line, monsters, &monstersSize);
    
    fgets(line, sizeof(line), stdin);
    parseArray(line, coins, &coinsSize);
    
    solution(heroes, heroesSize, monsters, monstersSize, coins, result);
    
    printf("[");
    for (int i = 0; i < heroesSize; i++) {
        printf("%d", result[i]);
        if (i < heroesSize-1) printf(",");
    }
    printf("]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × m)

For each of n heroes, we check all m monsters

✓ Linear Growth

Space Complexity

O(1)

Only using variables for iteration and sum calculation

✓ Linear Space

28.0K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler