Minimum Amount of Damage Dealt to Bob solution and explanation
9 more videos on this problem
3273. Minimum Amount of Damage Dealt to Bob | Biweekly Contest 138 | Leetcode | Easiest SolutionCodeFod · 15:27 · 1K views
Minimum Amount of Damage Dealt to Bob || LeetCode Biweekly Contest 138 || Leetcode Solutioncodi · 1:18 · 684 views
3273. Minimum Amount of Damage Dealt to Bob (Leetcode Hard)Programming Live with Larry · 19:56 · 634 views
3273. Minimum Amount of Damage Dealt to Bob || Biweekly Contest 138 || Sorting || PriorityQueueMohit Siwal · 17:13 · 245 views
Leetcode 3273 | Minimum Amount of Damage Dealt to Bob | Biweekly Contest 138Road To FAANG · 8:26 · 218 views
3273. Minimum Amount of Damage Dealt to Bob in Hindi || Leetcode Biweekly contest 138 || GeekstocodeGeekstocode · 20:11 · 197 views
3273. Minimum Amount of Damage Dealt to Bob | Biweekly Contest 138 | LeetcodeAmit Choraria · 11:38 · 130 views
3273. Minimum Amount of Damage Dealt to Bob || biweekly contest 138 || Leetcode Hard LolCode · 18:41 · 40 views
LeetCode 3273 | Minimum Amount of Damage Dealt to Bob | Biweekly contest 138CodingHelp · 22:45 · 25 views
Leetcode 3273. Minimum Amount of Damage Dealt to BobSolvedHardCompaniesCrowCode · 19:48 · 15 views
The problem
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 = 20points. - 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 = 12points. - Attack enemy 0 in the next second, after which enemy 0 will go down, the number of damage points dealt to Bob is
3points. - 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 = 4points.
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
4points. - 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 = 6points. - 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 = 6points. - 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 = 4points.
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] <= 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.
def minimum_damage(power, damage, health):
n = len(damage)
effective = [(damage[i] * (health[i] + power - 1) // power, i) for i in range(n)]
effective.sort(reverse=True, key=lambda x: (x[0], damage[x[1]]))
total_damage = 0
for eff, idx in effective:
total_damage += damage[idx] * (health[idx] + power - 1) // power
return total_damage
# Example usage:
print(minimum_damage(4, [1,2,3,4], [4,5,6,8])) # Output: 39import java.util.Arrays;
class Enemy implements Comparable<Enemy> {
int damage, health, effective;
Enemy(int damage, int health, int power) {
this.damage = damage;
this.health = health;
this.effective = damage * ((health + power - 1) / power);
}
@Override
public int compareTo(Enemy other) {
return other.effective - this.effective;
}
}
public class Main {
public static int minimumDamage(int power, int[] damage, int[] health) {
Enemy[] enemies = new Enemy[damage.length];
for (int i = 0; i < damage.length; i++) {
enemies[i] = new Enemy(damage[i], health[i], power);
}
Arrays.sort(enemies);
int totalDamage = 0;
for (Enemy enemy : enemies) {
totalDamage += enemy.damage * ((enemy.health + power - 1) / power);
}
return totalDamage;
}
public static void main(String[] args) {
int[] damage = {1, 2, 3, 4};
int[] health = {4, 5, 6, 8};
int power = 4;
System.out.println(minimumDamage(power, damage, health)); // Output: 39
}
}#include <iostream>
#include <vector>
#include <algorithm>
struct Enemy {
int damage, health, effective;
Enemy(int d, int h, int power) {
damage = d;
health = h;
effective = d * ((h + power - 1) / power);
}
};
bool compare(const Enemy &a, const Enemy &b) {
return a.effective > b.effective;
}
int minimumDamage(int power, std::vector<int> &damage, std::vector<int> &health) {
std::vector<Enemy> enemies;
for(size_t i = 0; i < damage.size(); ++i) {
enemies.emplace_back(damage[i], health[i], power);
}
std::sort(enemies.begin(), enemies.end(), compare);
int totalDamage = 0;
for(auto &enemy : enemies) {
totalDamage += enemy.damage * ((enemy.health + power - 1) / power);
}
return totalDamage;
}
int main() {
std::vector<int> damage = {1, 2, 3, 4};
std::vector<int> health = {4, 5, 6, 8};
int power = 4;
std::cout << minimumDamage(power, damage, health) << std::endl; // Output: 39
return 0;
}function minimumDamage(power, damage, health) {
const n = damage.length;
const enemies = [];
for (let i = 0; i < n; i++) {
const effective = damage[i] * Math.ceil(health[i] / power);
enemies.push({damage: damage[i], health: health[i], effective: effective});
}
enemies.sort((a, b) => b.effective - a.effective);
let totalDamage = 0;
for (let enemy of enemies) {
totalDamage += enemy.damage * Math.ceil(enemy.health / power);
}
return totalDamage;
}
// Example usage:
console.log(minimumDamage(4, [1, 2, 3, 4], [4, 5, 6, 8])); // Output: 39#include <stdio.h>
#include <stdlib.h>
typedef struct {
int damage;
int health;
int effective; // damage * (health + power - 1) / power
} Enemy;
int compare(const void *a, const void *b) {
Enemy *e1 = (Enemy *)a;
Enemy *e2 = (Enemy *)b;
return e2->effective - e1->effective;
}
int minimum_damage(int power, int* damage, int* health, int size) {
Enemy *enemies = (Enemy *)malloc(size * sizeof(Enemy));
for(int i = 0; i < size; i++) {
int effective_damage = damage[i] * ((health[i] + power - 1) / power);
enemies[i] = (Enemy) {damage[i], health[i], effective_damage};
}
qsort(enemies, size, sizeof(Enemy), compare);
int total_damage = 0;
for(int i = 0; i < size; i++) {
total_damage += enemies[i].damage * ((enemies[i].health + power - 1) / power);
}
free(enemies);
return total_damage;
}
int main() {
int damage[] = {1, 2, 3, 4};
int health[] = {4, 5, 6, 8};
int power = 4;
int size = 4;
printf("%d\n", minimum_damage(power, damage, health, size)); // Output: 39
return 0;
}using System;
using System.Linq;
class Enemy : IComparable<Enemy> {
public int Damage { get; }
public int Health { get; }
public int Effective { get; }
public Enemy(int damage, int health, int power) {
Damage = damage;
Health = health;
Effective = damage * ((health + power - 1) / power);
}
public int CompareTo(Enemy other) {
return other.Effective.CompareTo(this.Effective);
}
}
class Program {
public static int MinimumDamage(int power, int[] damage, int[] health) {
var enemies = damage.Select((t, i) => new Enemy(damage[i], health[i], power)).ToList();
enemies.Sort();
int totalDamage = enemies.Sum(enemy => enemy.Damage * ((enemy.Health + power - 1) / power));
return totalDamage;
}
static void Main() {
int[] damage = {1, 2, 3, 4};
int[] health = {4, 5, 6, 8};
int power = 4;
Console.WriteLine(MinimumDamage(power, damage, health)); // Output: 39
}
}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.
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.
def minimum_damage(power, damage, health):
n = len(damage)
ratios = [(damage[i] / health[i], i) for i in range(n)]
ratios.sort(reverse=True)
total_damage = 0
for _, idx in ratios:
hits = (health[idx] + power - 1) // power
total_damage += damage[idx] * hits
return total_damage
# Example usage:
print(minimum_damage(4, [1,2,3,4], [4,5,6,8])) # Output: 39import java.util.Arrays;
class Enemy implements Comparable<Enemy> {
double ratio;
int damage, health;
Enemy(int damage, int health) {
this.damage = damage;
this.health = health;
this.ratio = damage / (double) health;
}
@Override
public int compareTo(Enemy other) {
return Double.compare(other.ratio, this.ratio);
}
}
public class Main {
public static int minimumDamage(int power, int[] damage, int[] health) {
Enemy[] enemies = new Enemy[damage.length];
for (int i = 0; i < damage.length; i++) {
enemies[i] = new Enemy(damage[i], health[i]);
}
Arrays.sort(enemies);
int totalDamage = 0;
for (Enemy enemy : enemies) {
int hits = (enemy.health + power - 1) / power;
totalDamage += enemy.damage * hits;
}
return totalDamage;
}
public static void main(String[] args) {
int[] damage = {1, 2, 3, 4};
int[] health = {4, 5, 6, 8};
int power = 4;
System.out.println(minimumDamage(power, damage, health)); // Output: 39
}
}#include <iostream>
#include <vector>
#include <algorithm>
struct Enemy {
double ratio;
int damage;
int health;
Enemy(int d, int h) : damage(d), health(h) {
ratio = static_cast<double>(d) / h;
}
};
bool compare(const Enemy &a, const Enemy &b) {
return a.ratio > b.ratio;
}
int minimumDamage(int power, std::vector<int> &damage, std::vector<int> &health) {
std::vector<Enemy> enemies;
for(size_t i = 0; i < damage.size(); ++i) {
enemies.emplace_back(damage[i], health[i]);
}
std::sort(enemies.begin(), enemies.end(), compare);
int totalDamage = 0;
for(const auto &enemy : enemies) {
int hits = (enemy.health + power - 1) / power;
totalDamage += enemy.damage * hits;
}
return totalDamage;
}
int main() {
std::vector<int> damage = {1, 2, 3, 4};
std::vector<int> health = {4, 5, 6, 8};
int power = 4;
std::cout << minimumDamage(power, damage, health) << std::endl; // Output: 39
return 0;
}function minimumDamage(power, damage, health) {
const n = damage.length;
const enemies = [];
for (let i = 0; i < n; i++) {
const ratio = damage[i] / health[i];
enemies.push({damage: damage[i], health: health[i], ratio: ratio});
}
enemies.sort((a, b) => b.ratio - a.ratio);
let totalDamage = 0;
for (let enemy of enemies) {
const hits = Math.ceil(enemy.health / power);
totalDamage += enemy.damage * hits;
}
return totalDamage;
}
// Example usage:
console.log(minimumDamage(4, [1, 2, 3, 4], [4, 5, 6, 8])); // Output: 39#include <stdio.h>
#include <stdlib.h>
typedef struct {
double ratio;
int damage;
int health;
} Enemy;
int compare(const void *a, const void *b) {
Enemy *e1 = (Enemy *)a;
Enemy *e2 = (Enemy *)b;
if (e2->ratio > e1->ratio) return 1;
if (e2->ratio < e1->ratio) return -1;
return 0;
}
int minimum_damage(int power, int* damage, int* health, int size) {
Enemy *enemies = (Enemy *)malloc(size * sizeof(Enemy));
for(int i = 0; i < size; i++) {
enemies[i] = (Enemy) {damage[i] / (double)health[i], damage[i], health[i]};
}
qsort(enemies, size, sizeof(Enemy), compare);
int total_damage = 0;
for(int i = 0; i < size; i++) {
total_damage += enemies[i].damage * ((enemies[i].health + power - 1) / power);
}
free(enemies);
return total_damage;
}
int main() {
int damage[] = {1, 2, 3, 4};
int health[] = {4, 5, 6, 8};
int power = 4;
int size = 4;
printf("%d\n", minimum_damage(power, damage, health, size)); // Output: 39
return 0;
}using System;
using System.Linq;
class Enemy : IComparable<Enemy> {
public double Ratio { get; }
public int Damage { get; }
public int Health { get; }
public Enemy(int damage, int health) {
Damage = damage;
Health = health;
Ratio = (double)damage / health;
}
public int CompareTo(Enemy other) {
return other.Ratio.CompareTo(this.Ratio);
}
}
class Program {
public static int MinimumDamage(int power, int[] damage, int[] health) {
var enemies = damage.Select((t, i) => new Enemy(t, health[i])).ToList();
enemies.Sort();
int totalDamage = 0;
foreach (var enemy in enemies) {
int hits = (enemy.Health + power - 1) / power;
totalDamage += enemy.Damage * hits;
}
return totalDamage;
}
static void Main() {
int[] damage = {1, 2, 3, 4};
int[] health = {4, 5, 6, 8};
int power = 4;
Console.WriteLine(MinimumDamage(power, damage, health)); // Output: 39
}
}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.
Complexity comparison
| 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. |
Complexity analysis
| 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 |
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.