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.
This approach involves selecting the enemy based on the 'contribution' of an enemy until they are defeated. The contribution is calculated by (damage[i] * health[i]). The idea is to target enemies that deal the most potential damage first to minimize the total amount of damage dealt to Bob.
Calculate the effective total damage of each enemy by using their damage multiplied by the number of hits required to kill them, then prioritize enemy targets by this metric.
This Python code computes the 'effective' damage each enemy can deal if not taken out immediately. It sorts these by highest contribution and iterates over each, summing the damage taken by Bob. The overall damage dealt accumulates over a loop until all enemies are defeated.
The use of (health[i] + power - 1) // power ensures we calculate hits required accurately for the full defeat of an enemy.
Time Complexity: O(n log n), due to sorting of effective contributions.
Space Complexity: O(n), for storing effective contributions.
Another strategy focuses on eliminating the enemy with the maximum immediate damage output per health unit first. This ensures that the most damage-inflicting enemy is taken out as quickly as possible.
Calculate the damage-to-health ratio for each enemy and prioritize tackling those with the highest ratios, which can help reduce damage dealt to Bob across the first few rounds of attacks as efficiently as possible.
This Python approach entails calculating the damage to health ratio for each enemy, then sorting and prioritizing their defeat order by greatest ratio, focusing first on those who deal more immediate damage relative to health.
Time Complexity: O(n log n), due to sorting.
Space Complexity: O(n), for ratio list storage.
| Approach | Complexity |
|---|---|
| Approach 1: Greedy Approach Based on Contribution | Time Complexity: O(n log n), due to sorting of effective contributions. |
| Approach 2: Max Damage Per Hit Strategy | Time Complexity: O(n log n), due to sorting. |
| 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 |
3273. Minimum Amount of Damage Dealt to Bob | Biweekly Contest 138 | Leetcode | Easiest Solution • CodeFod • 975 views views
Watch 8 more video solutions →Practice Minimum Amount of Damage Dealt to Bob with our built-in code editor and test cases.
Practice on FleetCode