Skip to main content
Talentd

Minimum Amount of Damage Dealt to Bob - Solution & Explanation

HardArrayGreedySorting17 min readAsked at: Amazon
Practice this problem

Problem Statement

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:

  • Attack enemy 3 in the first two seconds, after which enemy 3 will go down, the number of damage points dealt to Bob is 10 + 10 = 20 points.
  • Attack enemy 2 in the next two seconds, after which enemy 2 will go down, the number of damage points dealt to Bob is 6 + 6 = 12 points.
  • Attack enemy 0 in the next second, after which enemy 0 will go down, the number of damage points dealt to Bob is 3 points.
  • Attack enemy 1 in the next two seconds, after which enemy 1 will go down, the number of damage points dealt to Bob is 2 + 2 = 4 points.

Example 2:

Input: power = 1, damage = [1,1,1,1], health = [1,2,3,4]

Output: 20

Explanation:

  • Attack enemy 0 in the first second, after which enemy 0 will go down, the number of damage points dealt to Bob is 4 points.
  • Attack enemy 1 in the next two seconds, after which enemy 1 will go down, the number of damage points dealt to Bob is 3 + 3 = 6 points.
  • Attack enemy 2 in the next three seconds, after which enemy 2 will go down, the number of damage points dealt to Bob is 2 + 2 + 2 = 6 points.
  • Attack enemy 3 in the next four seconds, after which enemy 3 will go down, the number of damage points dealt to Bob is 1 + 1 + 1 + 1 = 4 points.

Example 3:

Input: power = 8, damage = [40], health = [59]

Output: 320

 

Constraints:

  • 1 <= power <= 104
  • 1 <= n == damage.length == health.length <= 105
  • 1 <= damage[i], health[i] <= 104

Approach Overview

Problem 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 1: Approach 1: Greedy Approach Based on Contribution

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.

Code

PythonCJavaC++C#JavaScript

Python

C

Java

C++

C#

JavaScript

Complexity

Time Complexity: O(n log n), due to sorting of effective contributions.
Space Complexity: O(n), for storing effective contributions.

Try this approach in the editor →

Approach 2: Approach 2: Max Damage Per Hit Strategy

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.

Code

PythonCJavaC++C#JavaScript

Python

C

Java

C++

C#

JavaScript

Complexity

Time Complexity: O(n log n), due to sorting.
Space Complexity: O(n), for ratio list storage.

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Greedy Approach Based on Contribution

Time Complexity: O(n log n), due to sorting of effective contributions.
Space Complexity: O(n), for storing effective contributions.

Approach 2: Max Damage Per Hit Strategy

Time Complexity: O(n log n), due to sorting.
Space Complexity: O(n), for ratio list storage.

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy Based on ContributionO(n log n)O(n)General case when enemy order affects accumulated damage
Max Damage Per Hit StrategyO(n log n)O(n)Preferred explanation when framing the greedy rule as damage removed per hit

Video Solution

3273. Minimum Amount of Damage Dealt to Bob | Biweekly Contest 138 | Leetcode | Easiest Solution • CodeFod • 1,008 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimum Amount of Damage Dealt to Bob easy or hard?
Minimum Amount of Damage Dealt to Bob is classified as a Hard problem because the key step is recognizing the scheduling optimization hidden in the statement. Once you translate the objective to minimizing sum(weight × completion time), the greedy ordering rule becomes clear.
Minimum Amount of Damage Dealt to Bob Python/Java solution
Implementations in Python, Java, C++, and other languages follow the same pattern: compute hits needed for each enemy, sort enemies by damage divided by hits, then iterate to accumulate total damage based on completion time. The logic is language independent and relies on built-in sorting functions.
How to solve Minimum Amount of Damage Dealt to Bob in O(n)?
An O(n) solution is generally not feasible because the optimal strategy requires ordering enemies by a ratio metric. Determining this order requires sorting, which takes O(n log n) time in comparison-based algorithms. The rest of the computation after sorting is linear.
What is the best approach for Minimum Amount of Damage Dealt to Bob?
The optimal solution uses a greedy scheduling strategy. Compute the number of hits needed for each enemy and sort enemies by the ratio damage / hits in descending order. This ensures enemies that contribute the most damage per unit time are eliminated first. The approach runs in O(n log n) time due to sorting.
Is Minimum Amount of Damage Dealt to Bob asked at Google/Amazon/Meta?
Problems based on greedy scheduling and minimizing weighted completion time frequently appear in interviews at companies like Google, Amazon, and Meta. Variants often involve ordering tasks to minimize penalties or accumulated costs. This problem is a practical example of that pattern.
What data structure is used in Minimum Amount of Damage Dealt to Bob?
The solution primarily uses arrays or lists to store enemy attributes such as damage and required hits. A sorting step orders these elements based on a computed ratio like damage per hit. No advanced data structures beyond sorting and iteration are required.
What is the time complexity of Minimum Amount of Damage Dealt to Bob?
The optimal solution runs in O(n log n) time because enemies must be sorted by a greedy priority metric such as damage per hit. After sorting, a single linear pass computes the accumulated damage. Space complexity is O(n) for storing enemy attributes and hit counts.

Ready to solve this problem?

Practice Minimum Amount of Damage Dealt to Bob with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Penalty for a Shop

Next

Minimum Time to Complete Trips