Skip to main content
Talentd

Minimum Time to Kill All Monsters - Solution & Explanation

HardPremiumFree on FleetCodeArrayDynamic ProgrammingBit ManipulationBitmask17 min readAsked at: Trilogy
Practice this problem

Problem Statement

You are given an integer array power where power[i] is the power of the ith monster.

You start with 0 mana points, and each day you increase your mana points by gain where gain initially is equal to 1.

Each day, after gaining gain mana, you can defeat a monster if your mana points are greater than or equal to the power of that monster. When you defeat a monster:

  • your mana points will be reset to 0, and
  • the value of gain increases by 1.

Return the minimum number of days needed to defeat all the monsters.

 

Example 1:

Input: power = [3,1,4]
Output: 4
Explanation: The optimal way to beat all the monsters is to:
- Day 1: Gain 1 mana point to get a total of 1 mana point. Spend all mana points to kill the 2nd monster.
- Day 2: Gain 2 mana points to get a total of 2 mana points.
- Day 3: Gain 2 mana points to get a total of 4 mana points. Spend all mana points to kill the 3rd monster.
- Day 4: Gain 3 mana points to get a total of 3 mana points. Spend all mana points to kill the 1st monster.
It can be proven that 4 is the minimum number of days needed.

Example 2:

Input: power = [1,1,4]
Output: 4
Explanation: The optimal way to beat all the monsters is to:
- Day 1: Gain 1 mana point to get a total of 1 mana point. Spend all mana points to kill the 1st monster.
- Day 2: Gain 2 mana points to get a total of 2 mana points. Spend all mana points to kill the 2nd monster.
- Day 3: Gain 3 mana points to get a total of 3 mana points.
- Day 4: Gain 3 mana points to get a total of 6 mana points. Spend all mana points to kill the 3rd monster.
It can be proven that 4 is the minimum number of days needed.

Example 3:

Input: power = [1,2,4,9]
Output: 6
Explanation: The optimal way to beat all the monsters is to:
- Day 1: Gain 1 mana point to get a total of 1 mana point. Spend all mana points to kill the 1st monster.
- Day 2: Gain 2 mana points to get a total of 2 mana points. Spend all mana points to kill the 2nd monster.
- Day 3: Gain 3 mana points to get a total of 3 mana points.
- Day 4: Gain 3 mana points to get a total of 6 mana points.
- Day 5: Gain 3 mana points to get a total of 9 mana points. Spend all mana points to kill the 4th monster.
- Day 6: Gain 4 mana points to get a total of 4 mana points. Spend all mana points to kill the 3rd monster.
It can be proven that 6 is the minimum number of days needed.

 

Constraints:

  • 1 <= power.length <= 17
  • 1 <= power[i] <= 109

Approach Overview

Problem Overview: You are given an array where power[i] represents the strength of the i-th monster. Your weapon starts with power 1 and increases by 1 after every kill. Killing a monster with weapon power x takes ceil(power[i] / x) time. The order of kills changes the total time, so the task is to find the order that minimizes the total time needed to defeat all monsters.

Approach 1: State Compression + Memoization Search (O(n * 2^n) time, O(2^n) space)

The key observation: the only thing that matters at any moment is which monsters have already been killed. Represent this state using a bitmask where bit i indicates whether monster i is defeated. The number of killed monsters k determines the current weapon power (k + 1). Use depth‑first search with memoization: from a given mask, try killing every remaining monster. For each candidate i, compute the time ceil(power[i] / (k + 1)), then recurse on the new mask. Memoize results for each mask to avoid recomputing overlapping states. This is a classic bitmask state search where each state branches to remaining monsters. With memoization, every mask is evaluated once and transitions try up to n monsters.

Approach 2: State Compression + Dynamic Programming (O(n * 2^n) time, O(2^n) space)

This approach converts the recursive idea into bottom‑up dynamic programming. Let dp[mask] store the minimum time required to defeat the set of monsters represented by mask. The number of set bits k determines the weapon power when the next monster is attacked: k monsters already killed means the next attack uses power k. For each mask, iterate through monsters not yet killed and update the next state: nextMask = mask | (1 << i). The transition cost is ceil(power[i] / k) where k = popcount(mask) + 1. Update dp[nextMask] with the minimum possible time. Iterate masks from small to large so previous states are already computed. The final answer is dp[(1 << n) - 1], meaning all monsters are defeated.

The bitmask representation is what makes the problem tractable. Without it, enumerating all permutations would require O(n!) time. State compression reduces the search to 2^n states while still capturing the effect of order through the increasing weapon power.

Recommended for interviews: The state compression dynamic programming solution is typically expected. It shows you recognize permutation-style optimization problems and convert them into 2^n DP states. Mentioning the DFS + memoization variant demonstrates understanding of the same state transition from a top‑down perspective, while the bottom‑up DP implementation highlights mastery of bitmask DP patterns frequently asked in hard interview problems.

Approach 1: State Compression + Memoization Search

We note that the number of monsters is at most 17, which means we can use a 17-bit binary number to represent the state of the monsters. The i-th bit being 1 indicates that the i-th monster is still alive, and 0 indicates that the i-th monster has been defeated.

We design a function dfs(mask) to represent the minimum number of days needed to defeat all monsters when the current state of the monsters is mask. The answer is dfs(2^n - 1), where n is the number of monsters.

The calculation of the function dfs(mask) is as follows:

  • If mask = 0, it means all monsters have been defeated, return 0;
  • Otherwise, we enumerate each monster i. If the i-th monster is still alive, we can choose to defeat the i-th monster, then recursively calculate dfs(mask \oplus 2^i), and update the answer to ans = min(ans, dfs(mask \oplus 2^i) + \lceil \frac{x}{gain} \rceil), where x is the strength of the i-th monster, and gain = 1 + (n - mask.bit_count()) represents the current daily mana gain.

Finally, we return dfs(2^n - 1).

The time complexity is O(2^n times n), and the space complexity is O(2^n). Here, n is the number of monsters.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Approach 2: State Compression + Dynamic Programming

We can convert the memoization search in Solution 1 to dynamic programming. Define f[mask] to represent the minimum number of days needed to defeat all monsters when the current state of the monsters is mask. Here, mask is an n-bit binary number, where the i-th bit being 1 indicates that the i-th monster has been defeated, and 0 indicates that the i-th monster is still alive. Initially, f[0] = 0, and the rest f[mask] = +infty. The answer is f[2^n - 1].

We enumerate mask in the range [1, 2^n - 1]. For each mask, we enumerate each monster i. If the i-th monster is defeated, it can be transferred from the previous state mask \oplus 2^i, with a transfer cost of (power[i] + gain - 1) / gain, where gain = mask.bitCount().

Finally, return f[2^n - 1].

The time complexity is O(2^n times n), and the space complexity is O(2^n). Here, n is the number of monsters.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
State Compression + Memoization Search—
State Compression + Dynamic Programming—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
State Compression + Memoization SearchO(n * 2^n)O(2^n)Good when reasoning about the problem recursively and exploring monster orders via DFS.
State Compression + Dynamic ProgrammingO(n * 2^n)O(2^n)Preferred for interviews and production solutions when n ≤ 17 and you want deterministic bottom‑up computation.

Video Solution

【每日一题】LeetCode 2403. Minimum Time to Kill All Monsters • Huifeng Guan • 225 views views

Watch 1 more video solutions →

Frequently Asked Questions

Is Minimum Time to Kill All Monsters easy or hard?
Minimum Time to Kill All Monsters is classified as Hard on LeetCode. The difficulty comes from recognizing that the order of actions affects the result and converting a factorial permutation search into an efficient O(n * 2^n) bitmask DP solution.
Minimum Time to Kill All Monsters Python/Java solution
Most implementations use bitmask DP or DFS with memoization. The logic is identical across languages: iterate through all masks, compute the current weapon power using popcount, and update dp[nextMask] with ceil(power[i] / currentPower). Python, Java, C++, Go, and TypeScript implementations follow the same transition pattern.
How to solve Minimum Time to Kill All Monsters in O(n * 2^n)?
Use bitmask dynamic programming. Let dp[mask] represent the minimum time to defeat the monsters in that subset. Count how many monsters are already defeated using popcount(mask) to determine current weapon power, then try defeating each remaining monster and update the next mask with the computed time cost.
What is the best approach for Minimum Time to Kill All Monsters?
Bitmask dynamic programming is the most effective approach. Represent the set of defeated monsters as a bitmask and compute the minimum time for each state. For every state, try killing each remaining monster and update the next state. This reduces the permutation search from O(n!) to O(n * 2^n).
Is Minimum Time to Kill All Monsters asked at Google/Amazon/Meta?
Problems involving bitmask dynamic programming and permutation optimization appear frequently in interviews at companies like Google, Amazon, and Meta. This problem tests understanding of state compression, subset transitions, and DP over subsets.
What data structure is used in Minimum Time to Kill All Monsters?
The core data structure is a bitmask representing subsets of monsters. The algorithm also uses a DP array or memoization map indexed by mask to store the minimum time required for each subset state.
What is the time complexity of Minimum Time to Kill All Monsters?
The optimal solution runs in O(n * 2^n) time and O(2^n) space. There are 2^n possible subsets of monsters, and for each subset the algorithm may try up to n transitions when selecting the next monster to defeat.

Ready to solve this problem?

Practice Minimum Time to Kill All Monsters with our built-in code editor and test cases.

Practice on FleetCode
Previous

Closest Room

Next

Eliminate Maximum Number of Monsters