Eliminate Maximum Number of Monsters

Eliminate Maximum Number of Monsters

1. What is this problem about?

The Eliminate Maximum Number of Monsters coding problem is a strategic survival challenge that tests your ability to prioritize tasks under pressure. Imagine you are defending a city from a wave of monsters approaching at different speeds. You have a weapon that can eliminate one monster per minute, but it needs time to recharge. Each monster starts at a certain distance and moves toward the city at a constant velocity. Your goal is to determine the maximum number of monsters you can defeat before any of them reaches the city. If a monster reaches the city at the same time you are able to fire, you lose.

2. Why is this asked in interviews?

Companies like Google and Meta frequently use the Eliminate Maximum Number of Monsters interview question to evaluate a candidate's grasp of greedy algorithms and sorting. It requires more than just basic array manipulation; it demands an understanding of how to transform raw data (distance and speed) into a more useful metric (time to arrival). This problem mirrors real-world scenarios where resources (like CPU time or bandwidth) are limited, and you must decide the optimal order to process incoming requests to prevent system failure.

3. Algorithmic pattern used

The primary topics interview pattern for this problem is the Greedy Algorithm combined with Sorting. By calculating the time each monster takes to reach the city (time = distance / speed), you can sort these times in ascending order. The greedy choice is always to eliminate the monster that will arrive earliest. If you can eliminate the $i$-th monster before $i$ minutes have passed, you continue; otherwise, you've reached your limit.

4. Example explanation

Suppose three monsters are approaching:

• Monster A: Distance 5, Speed 1 (Arrives in 5 minutes)
• Monster B: Distance 2, Speed 2 (Arrives in 1 minute)
• Monster C: Distance 3, Speed 1 (Arrives in 3 minutes)

Sorted arrival times: [1, 3, 5].

• Minute 0: You eliminate the monster arriving at minute 1 (Monster B).
• Minute 1: You eliminate the monster arriving at minute 3 (Monster C).
• Minute 2: You eliminate the monster arriving at minute 5 (Monster A). In this case, you eliminate all 3 monsters. If Monster B had a speed of 4, it would arrive in 0.5 minutes, and you would lose immediately because it reaches the city before you can fire your first shot at minute 0.

5. Common mistakes candidates make

• Integer Division: Forgetting that distance divided by speed can result in a fraction. While many implementations use integer ceilings, it's safer to think in terms of floating-point or to compare distance < speed * time.
• Timing Off-by-One: Miscalculating when the weapon is ready. You fire at $t=0, 1, 2...$ and the monster must not arrive at or before that time if they are not the one being shot.
• Sorting the wrong property: Attempting to sort by distance or speed alone rather than the calculated arrival time.

6. Interview preparation tip

When tackling problems involving "arrival times" or "deadlines," always consider transforming the input into a single "time-to-event" metric. This often simplifies a multi-variable problem into a single-variable sorting task. Practice explaining why a greedy approach works here: because killing a monster that arrives later instead of one that arrives sooner never improves your chances of survival.