Minimum Initial Strength to Defeat All Monsters Python solution

Implement binary search with a helper function to check if a given strength can defeat all monsters. The solution is concise and runs in O(n log m) time.

Is Minimum Initial Strength to Defeat All Monsters easy or hard?

The problem is rated Medium with a 50.7% acceptance rate. It requires understanding of binary search and careful simulation of the battle sequence.

How to solve Minimum Initial Strength to Defeat All Monsters in O(n log m)?

Use binary search on the strength range. For each mid value, simulate the battle sequence to check if it can defeat all monsters. Adjust the search range based on the result.

What is the best approach for Minimum Initial Strength to Defeat All Monsters?

The optimal approach is binary search with a time complexity of O(n log m). It efficiently narrows down the minimum strength required by checking mid values in the possible range.

Is Minimum Initial Strength to Defeat All Monsters asked at Google/Amazon/Meta?

This problem tests binary search and simulation skills, which are common in technical interviews at top companies like Google and Amazon.

What data structure is used in Minimum Initial Strength to Defeat All Monsters?

No additional data structures are needed. The solution relies on binary search and iterative simulation to determine the minimum strength.

What is the time complexity of Minimum Initial Strength to Defeat All Monsters?

The best solution achieves O(n log m) time complexity using binary search. The brute force approach runs in O(n * m) time, which is inefficient for large inputs.

Description Hints 3 Solution Video 19:16

4008. Minimum Initial Strength to Defeat All Monsters

Medium50.1% acceptance

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

You are also given a 2D integer array boosts, where boosts[i] = [l_i, r_i, v_i] indicates that v_i is added to your temporary bonus while fighting any monster whose index lies in [l_i, r_i]. 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 * 10⁴
1 <= monsters[i] <= 10⁹
0 <= boosts.length <= 5 * 10⁴
boosts[i] == [l_i, r_i, v_i]
0 <= l_i <= r_i < monsters.length
1 <= v_i <= 10⁹

Topics

Hints open one at a time

Hint 1

Use a difference array to compute the total temporary bonus applied at every monster.

Hint 2

Before fighting monster i, your current strength is max(0, initialStrength - prefixSum), where prefixSum is the total strength of all previously defeated monsters.

Hint 3

If bonus[i] < monsters[i], then the initial strength must be at least prefixSum + monsters[i] - bonus[i]. Take the maximum of this value over all monsters.

19:16

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def minInitialStrength(self, monsters: list[int], boosts: list[list[int]]) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[5,10,15]
[[1,1,10]]

Input

[5,10,15]
[[1,2,10],[1,2,5]]

Your code is saved on this device.Solution