Minimum Initial Strength to Defeat All Monsters solution and explanation
The problem
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
bonusbe the sum of the values of all boosts that apply to monsteri. - You can defeat the monster only if your current strength plus
bonusis at leastmonsters[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. Since30 + 0 >= 5, this monster can be defeated. The strength becomes30 - 5 = 25.monsters[1] = 10: At index 1, the bonus is 10. Since25 + 10 >= 10, this monster can be defeated. The strength becomes25 - 10 = 15.monsters[2] = 15: At index 2, the bonus is 0. Since15 + 0 >= 15, this monster can be defeated. The strength becomes15 - 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. Since5 + 0 >= 5, the monster can be defeated. The strength becomes5 - 5 = 0.monsters[1] = 10: The two overlapping boosts providebonus = 10 + 5 = 15. Since0 + 15 >= 10, the monster can be defeated. The strength remains 0.monsters[2] = 15: The two overlapping boosts again providebonus = 15. Since0 + 15 >= 15, the monster can be defeated. The strength remains 0.
Thus, the minimum initial strength required is 5.
Constraints:
1 <= monsters.length <= 5 * 1041 <= monsters[i] <= 1090 <= boosts.length <= 5 * 104boosts[i] == [li, ri, vi]0 <= li <= ri < monsters.length1 <= vi <= 109
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.
Solution
Each boost adds a value to an entire index range [l, r], so we first apply all boosts using a difference array d. The 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 bonus (the prefix sum of the difference array); if v + bonus < monsters[i], the monster cannot be defeated and v is infeasible; otherwise, we defeat it, decrease v by 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.
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 lclass 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;
}
}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;
}
};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;
}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
}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 |
Frequently asked questions
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.