Minimum Initial Strength to Defeat All Monsters - Video Solutions

MediumArrayBinary SearchGreedyPrefix Sum

Practice this problem Read Solution

LeetCode 4008 | Weekly Contest 512 Q3 | Minimum Initial Strength to Defeat All Monsters 🤯

19:1663 views

2 video solutions available

Minimum Initial Strength to Defeat All Monsters - Video Solution

Watch 2 video solutions for Minimum Initial Strength to Defeat All Monsters, a medium level problem involving Array, Binary Search, Greedy. This walkthrough by CodeSprint has 63 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.

Problem Statement

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⁹

Read full problem with examples

Approach Overview

Problem Overview: You need to determine the smallest initial strength value that allows you to defeat all monsters in order. Each monster has health and attack values; your strength must be ≥ monster's health to defeat it, then decreases by the attack value.

Approach 1: Brute Force (O(n * m))

Check every possible strength value starting from 1 until you find the minimum that works. For each candidate strength, simulate the battle sequence. This approach is straightforward but inefficient for large inputs.

Approach 2: Binary Search (O(n log m))

Use binary search to find the minimum valid strength between 1 and maximum possible required strength. For each mid value, check if it can defeat all monsters. This reduces the search space exponentially compared to linear search.

Recommended for interviews: Interviewers expect the binary search solution. It demonstrates understanding of optimization techniques and efficient search algorithms. Mentioning the brute force shows problem comprehension, but solving with binary search highlights analytical skills.

Complexity Analysis

Approach	Time	Space	When to Use
Brute Force	O(n * m)	O(1)	Small input sizes
Binary Search	O(n log m)	O(1)	General case

Continue Learning

Practice this problem

Solve it on FleetCode

Read Solution & Explanation

Detailed text walkthrough