Skip to content

4008. Minimum Initial Strength to Defeat All Monsters

Description

You are given an integer array monsters, where monsters[i] represents the strength of the ith monster.

You are also given a 2D integer array boosts, where boosts[i] = [li, ri, vi] indicates that vi is added to your temporary bonus while fighting any monster whose index lies in [li, ri]. Boost ranges may overlap, and the values of all applicable boosts are added together.

You start with a non-negative initial strength and fight the monsters from left to right.

For each monster at index i:

  • Let bonus be the sum of the values of all boosts that apply to monster i.
  • You can defeat the monster only if your current strength plus bonus is at least monsters[i].
  • After defeating the monster, only your current strength decreases by monsters[i]. If it becomes negative, it is set to 0.

Return the minimum initial strength required to defeat all monsters.

Note: The temporary bonus is used only to determine whether the current monster can be defeated. It does not otherwise change your current strength.

Β 

Example 1:

Input: monsters = [5,10,15], boosts = [[1,1,10]]

Output: 30

Explanation:

Let's start with an initial strength of 30.

  • monsters[0] = 5: At index 0, the bonus is 0. Since 30 + 0 >= 5, this monster can be defeated. The strength becomes 30 - 5 = 25.
  • monsters[1] = 10: At index 1, the bonus is 10. Since 25 + 10 >= 10, this monster can be defeated. The strength becomes 25 - 10 = 15.
  • monsters[2] = 15: At index 2, the bonus is 0. Since 15 + 0 >= 15, this monster can be defeated. The strength becomes 15 - 15 = 0.

Thus, the minimum initial strength required is 30.

Example 2:

Input: monsters = [5,10,15], boosts = [[1,2,10],[1,2,5]]

Output: 5

Explanation:

Let's start with an initial strength of 5.

  • monsters[0] = 5: The bonus is 0. Since 5 + 0 >= 5, the monster can be defeated. The strength becomes 5 - 5 = 0.
  • monsters[1] = 10: The two overlapping boosts provide bonus = 10 + 5 = 15. Since 0 + 15 >= 10, the monster can be defeated. The strength remains 0.
  • monsters[2] = 15: The two overlapping boosts again provide bonus = 15. Since 0 + 15 >= 15, the monster can be defeated. The strength remains 0.

Thus, the minimum initial strength required is 5.

Β 

Constraints:

  • 1 <= monsters.length <= 5 * 104
  • 1 <= monsters[i] <= 109
  • 0 <= boosts.length <= 5 * 104
  • boosts[i] == [li, ri, vi]
  • 0 <= li <= ri < monsters.length
  • 1 <= vi <= 109​​​​​​​

Solutions

Each boost adds a value to an entire index range \([l, r]\), so we first apply all boosts using a difference array \(d\). The \(\textit{bonus}\) when fighting the \(i\)-th monster is then the prefix sum \(\sum_{j=0}^{i} d[j]\).

Next, we binary search the initial strength \(v\). For a given \(v\), we simulate the fights from left to right: maintain the current \(\textit{bonus}\) (the prefix sum of the difference array); if \(v + \textit{bonus} < \textit{monsters}[i]\), the monster cannot be defeated and \(v\) is infeasible; otherwise, we defeat it, decrease \(v\) by \(\textit{monsters}[i]\), and reset \(v\) to \(0\) if it becomes negative. If all monsters can be defeated, \(v\) is feasible.

A larger initial strength never makes it harder to defeat all monsters, so feasibility is monotonic in \(v\), and we can binary search the minimum feasible initial strength. The upper bound of the search is set to \(10^{15}\) (the total strength of all monsters is at most \(5 \times 10^4 \times 10^9 = 5 \times 10^{13}\)).

The time complexity is \(O((n + m) \times \log M)\), and the space complexity is \(O(n)\), where \(n\) is the number of monsters, \(m\) is the number of boosts, and \(M = 10^{15}\) is the upper bound of the binary search.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def minInitialStrength(self, monsters: list[int], boosts: list[list[int]]) -> int:
        def check(v: int) -> bool:
            bonus = 0
            for a, b in zip(monsters, d):
                bonus += b
                if v + bonus < a:
                    return False
                v -= a
                v = max(v, 0)
            return True

        n = len(monsters)
        d = [0] * (n + 1)
        for l, r, v in boosts:
            d[l] += v
            d[r + 1] -= v

        l, r = 0, 10**15
        while l < r:
            mid = (l + r) >> 1
            if check(mid):
                r = mid
            else:
                l = mid + 1
        return l

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
    private int[] monsters;
    private long[] d;

    public long minInitialStrength(int[] monsters, int[][] boosts) {
        this.monsters = monsters;
        int n = monsters.length;
        d = new long[n + 1];
        for (int[] b : boosts) {
            d[b[0]] += b[2];
            d[b[1] + 1] -= b[2];
        }

        long left = 0, right = (long) 1e15;
        while (left < right) {
            long mid = (left + right) >>> 1;
            if (check(mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    private boolean check(long v) {
        long bonus = 0;
        for (int i = 0; i < monsters.length; i++) {
            bonus += d[i];
            if (v + bonus < monsters[i]) {
                return false;
            }
            v -= monsters[i];
            if (v < 0) {
                v = 0;
            }
        }
        return true;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    long long minInitialStrength(vector<int>& monsters, vector<vector<int>>& boosts) {
        int n = monsters.size();
        vector<long long> d(n + 1);
        for (auto& b : boosts) {
            d[b[0]] += b[2];
            d[b[1] + 1] -= b[2];
        }

        auto check = [&](long long v) -> bool {
            long long bonus = 0;
            for (int i = 0; i < n; i++) {
                bonus += d[i];
                if (v + bonus < monsters[i]) {
                    return false;
                }
                v -= monsters[i];
                if (v < 0) {
                    v = 0;
                }
            }
            return true;
        };

        long long left = 0, right = 1000000000000000LL;
        while (left < right) {
            long long mid = (left + right) / 2;
            if (check(mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
func minInitialStrength(monsters []int, boosts [][]int) int64 {
    n := len(monsters)
    d := make([]int64, n+1)
    for _, b := range boosts {
        d[b[0]] += int64(b[2])
        d[b[1]+1] -= int64(b[2])
    }

    check := func(v int64) bool {
        var bonus int64
        for i, a := range monsters {
            bonus += d[i]
            if v+bonus < int64(a) {
                return false
            }
            v -= int64(a)
            if v < 0 {
                v = 0
            }
        }
        return true
    }

    var left, right int64 = 0, 1000000000000000
    for left < right {
        mid := (left + right) / 2
        if check(mid) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
function minInitialStrength(monsters: number[], boosts: number[][]): number {
    const n = monsters.length;
    const d = new Array<number>(n + 1).fill(0);

    for (const [l, r, v] of boosts) {
        d[l] += v;
        d[r + 1] -= v;
    }

    const check = (v: number): boolean => {
        let bonus = 0;
        for (let i = 0; i < n; i++) {
            bonus += d[i];
            if (v + bonus < monsters[i]) {
                return false;
            }
            v -= monsters[i];
            if (v < 0) {
                v = 0;
            }
        }
        return true;
    };

    let left = 0;
    let right = 1e15;
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        if (check(mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

Comments