Minimum Amount of Damage Dealt to Bob

Hard
1435.

Minimum Amount of Damage Dealt to Bob

Minimum Amount of Damage Dealt to Bob is a hard coding problem on arrays, sorting and greedy, asked in Amazon and Google interviews.

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^4
  • 1 <= n == damage.length == health.length <= 300
  • 1 <= damage[i], health[i] <= 100
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} power
 * @param {number[]} damage
 * @param {number[]} health
 * @return {number}
 */
var minDamage = function(power, damage, health) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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^4
  • 1 <= n == damage.length == health.length <= 300
  • 1 <= damage[i], health[i] <= 100

Hints for Minimum Amount of Damage Dealt to Bob

  1. Hint 1

    Enemy i needs t_i = ceil(health[i] / power) strikes, and finishing it before switching is never worse than splitting the strikes.

  2. Hint 2

    If enemy i dies at second T_i, Bob takes damage[i] * T_i from it, so the total is sum(damage[i] * T_i) — a weighted completion-time problem.

  3. Hint 3

    Compare two adjacent enemies a and b: a should go first exactly when t_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

  1. Compute t_i = ceil(health[i] / power) for every enemy.
  2. Sort the enemies so that a precedes b when t_a * damage_b < t_b * damage_a (cross-multiplied to stay in integers).
  3. Walk the order with a clock: add t_i to the clock, then add damage[i] * clock to 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 total

Java

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