Minimum Amount of Damage Dealt to Bob — Problem & Solution
Minimum Amount of Damage Dealt to Bob solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Minimum Amount of Damage Dealt to Bob is a hard coding problem on arrays, sorting and greedy, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Arrays, Sorting, Greedy
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Bob faces n enemies. Enemy i deals damage[i] points of damage to Bob every second while its health is above zero, and starts with health[i] health.
Every second, first all living enemies hit Bob, and then Bob strikes one living enemy of his choice, removing power health from it. An enemy whose health drops to 0 or below dies and deals no more damage.
Return the minimum total damage Bob takes before all enemies are dead.
Constraint note: the sizes are capped (n <= 300, damage[i], health[i] <= 100; the original allows 10^5 and 10^4) so the total fits in a 32-bit integer.
Example 1
Input: power = 3, damage = [2,5], health = [7,3]
Output: 13
Explanation: Kill enemy 1 first (1 second, Bob takes 2 + 5), then enemy 0 needs 3 more seconds at 2 damage each: 7 + 6 = 13.
Example 2
Input: power = 4, damage = [1,2,3,4], health = [4,5,6,8]
Output: 39
Example 3
Input: power = 8, damage = [40], health = [59]
Output: 320
Constraints
1 <= power <= 10^41 <= n == damage.length == health.length <= 3001 <= damage[i], health[i] <= 100
Hints for Minimum Amount of Damage Dealt to Bob
Hint 1
Enemy
ineedst_i = ceil(health[i] / power)strikes, and finishing it before switching is never worse than splitting the strikes.Hint 2
If enemy
idies at secondT_i, Bob takesdamage[i] * T_ifrom it, so the total issum(damage[i] * T_i)— a weighted completion-time problem.Hint 3
Compare two adjacent enemies
aandb:ashould go first exactly whent_a * damage_b < t_b * damage_a. Sort by that rule.
How to solve Minimum Amount of Damage Dealt to Bob
Each enemy is a job of length t_i = ceil(health[i] / power) seconds with weight damage[i], and the damage Bob takes is the weighted sum of completion times. Smith's rule — order by t / damage ascending — minimises it.
Approach
- Compute
t_i = ceil(health[i] / power)for every enemy. - Sort the enemies so that
aprecedesbwhent_a * damage_b < t_b * damage_a(cross-multiplied to stay in integers). - Walk the order with a clock: add
t_ito the clock, then adddamage[i] * clockto the total.
Why it works
Swapping adjacent enemies a then b only changes their two terms: with a first the pair costs d_a * t_a + d_b * (t_a + t_b) extra over the common prefix, with b first d_b * t_b + d_a * (t_a + t_b). The difference is d_b * t_a - d_a * t_b, so a belongs first exactly when t_a * d_b <= t_b * d_a. Any order violating the rule can be improved by such a swap, so the sorted order is optimal. Interleaving strikes only delays some enemy's death without hastening any other's.
Complexity
- Time —
O(n log n) - Space —
O(n)
Pitfalls
- Sorting by damage alone or by health alone fails; it is the ratio that matters.
- Use the strike count
ceil(health / power), not the raw health. - An enemy still deals damage during the second in which it is killed — its completion time counts in full.
Reference solution
Python
from typing import List
from functools import cmp_to_key
def minDamage(power: int, damage: List[int], health: List[int]) -> int:
t = [(h + power - 1) // power for h in health]
# a goes before b when t[a] / damage[a] < t[b] / damage[b]
order = sorted(range(len(damage)), key=cmp_to_key(lambda a, b: t[a] * damage[b] - t[b] * damage[a]))
clock = total = 0
for i in order:
clock += t[i]
total += damage[i] * clock
return totalJava
public static int minDamage(int power, int[] damage, int[] health) {
int n = damage.length;
int[] t = new int[n];
Integer[] order = new Integer[n];
for (int i = 0; i < n; i++) {
t[i] = (health[i] + power - 1) / power;
order[i] = i;
}
// a goes before b when t[a] / damage[a] < t[b] / damage[b]
Arrays.sort(order, (a, b) -> Long.compare((long) t[a] * damage[b], (long) t[b] * damage[a]));
long clock = 0, total = 0;
for (int i : order) {
clock += t[i];
total += damage[i] * clock;
}
return (int) total;
}C++
int minDamage(int power, vector<int>& damage, vector<int>& health) {
int n = damage.size();
vector<long long> t(n);
vector<int> order(n);
for (int i = 0; i < n; i++) {
t[i] = (health[i] + power - 1) / power;
order[i] = i;
}
// a goes before b when t[a] / damage[a] < t[b] / damage[b]
sort(order.begin(), order.end(), [&](int a, int b) { return t[a] * damage[b] < t[b] * damage[a]; });
long long clock = 0, total = 0;
for (int i : order) {
clock += t[i];
total += damage[i] * clock;
}
return (int) total;
}JavaScript
var minDamage = function(power, damage, health) {
var n = damage.length;
var t = [], order = [];
for (var i = 0; i < n; i++) {
t.push(Math.floor((health[i] + power - 1) / power));
order.push(i);
}
// a goes before b when t[a] / damage[a] < t[b] / damage[b]
order.sort(function(a, b) { return t[a] * damage[b] - t[b] * damage[a]; });
var clock = 0, total = 0;
for (var k = 0; k < n; k++) {
clock += t[order[k]];
total += damage[order[k]] * clock;
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms