Minimum Time to Kill All Monsters - Video Solutions

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.