Leetcode Problem 2838. Maximum Coins Heroes Can Collect

2838. Maximum Coins Heroes Can Collect

Leetcode Solutions

Sort, Prefix Sum, and Binary Search

  1. Sort the monsters array and the heroes array in ascending order.
  2. Create a prefix_sum array where prefix_sum[i] represents the total number of coins that can be earned by defeating the first i monsters.
  3. Initialize an array ans to store the maximum coins each hero can collect.
  4. For each hero, use binary search to find the rightmost monster that the hero can defeat based on the hero's power.
  5. Use the index from the binary search to look up the prefix_sum array and assign the value to the corresponding index in ans.
  6. Return the ans array.
UML Thumbnail

Brute Force with Sorting

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...