Watch 9 video solutions for Minimum Amount of Damage Dealt to Bob, a hard level problem involving Array, Greedy, Sorting. This walkthrough by CodeFod has 975 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an integer power and two integer arrays damage and health, both having length n.
Bob has n enemies, where enemy i will deal Bob damage[i] points of damage per second while they are alive (i.e. health[i] > 0).
Every second, after the enemies deal damage to Bob, he chooses one of the enemies that is still alive and deals power points of damage to them.
Determine the minimum total amount of damage points that will be dealt to Bob before all n enemies are dead.
Example 1:
Input: power = 4, damage = [1,2,3,4], health = [4,5,6,8]
Output: 39
Explanation:
10 + 10 = 20 points.6 + 6 = 12 points.3 points.2 + 2 = 4 points.Example 2:
Input: power = 1, damage = [1,1,1,1], health = [1,2,3,4]
Output: 20
Explanation:
4 points.3 + 3 = 6 points.2 + 2 + 2 = 6 points.1 + 1 + 1 + 1 = 4 points.Example 3:
Input: power = 8, damage = [40], health = [59]
Output: 320
Constraints:
1 <= power <= 1041 <= n == damage.length == health.length <= 1051 <= damage[i], health[i] <= 104Problem Overview: You fight multiple enemies. Each enemy deals a fixed amount of damage to Bob every second until it dies. Killing an enemy requires several hits depending on its health and your attack power. The order you eliminate enemies determines how long each one keeps damaging Bob. The goal is to minimize the total damage Bob receives.
Approach 1: Greedy Based on Contribution (O(n log n) time, O(n) space)
First compute how many hits are required to kill each enemy: hits = ceil(health / power). If an enemy stays alive longer, its damage per second contributes repeatedly to the total. The total damage becomes sum(damage[i] * completion_time[i]), where completion time is the cumulative hits spent before that enemy dies. This turns the problem into a classic scheduling optimization: minimize weighted completion time. Sort enemies by the ratio hits / damage (equivalently by damage / hits in descending order). Enemies with higher damage contribution per hit are removed first. After sorting, iterate and accumulate completion time to compute total damage. Sorting dominates the complexity: O(n log n) time and O(n) space. This approach combines ideas from Greedy strategies and Sorting over derived metrics.
Approach 2: Max Damage Per Hit Strategy (O(n log n) time, O(n) space)
Another way to view the same insight is to maximize the damage removed from the battlefield per hit spent. For each enemy, calculate hits = ceil(health / power) and evaluate its efficiency as damage / hits. This value represents how much damage per second disappears for every hit invested. Sort enemies in descending order of this metric. Process enemies in that order, track cumulative hits, and add damage[i] * elapsed_time to the total before each one dies. The logic is identical to Smith's rule in scheduling theory. The algorithm still runs in O(n log n) time due to sorting and uses O(n) space to store enemy data. Arrays are the main structure, so familiarity with Array manipulation is enough.
Recommended for interviews: The greedy ordering by damage / hits is the expected solution. Interviewers look for recognition that the objective is minimizing sum(weight * completion_time), which leads directly to sorting by contribution ratio. Explaining the reasoning before coding demonstrates stronger algorithmic understanding than jumping straight to implementation.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Based on Contribution | O(n log n) | O(n) | General case when enemy order affects accumulated damage |
| Max Damage Per Hit Strategy | O(n log n) | O(n) | Preferred explanation when framing the greedy rule as damage removed per hit |