⚡Flashcard Drill➔
NeetCode #797LC-1921MediumGreedy
← Back to All Problems

#797 · #1921 · Eliminate Maximum Number of Monsters(消灭怪物的最大数量)

📌 Problem Statement & Constraints

You are given dist[i] (distance from the city) and speed[i] (speed per minute) for n monsters. Each minute you may eliminate one monster; a monster reaching the city ends the game. Return the maximum number of monsters eliminated. Constraints: 1 <= n <= 10^5, 1 <= dist[i], speed[i] <= 10^5.

💡 Core Algorithmic Approaches

  1. Monster i arrives after ceil(dist[i] / speed[i]) minutes.
  2. You kill one monster per minute, starting at minute 0, so the i-th killed monster (0-indexed) is killed at minute i.
  3. Sort the arrival times; kill the soonest arrivals first.
  4. If the i-th soonest arrival is at or before minute i, it has already reached the city, so you have eliminated i monsters.

💻 Benchmark Python3 Implementation

class Solution:
    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:
        arrival = sorted((d + s - 1) // s for d, s in zip(dist, speed))
        for i, t in enumerate(arrival):
            if t <= i:                 # this monster already arrived
                return i
        return len(dist)

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n log n): sorting the arrival times dominates.
💾 Space Complexity
O(n): the arrival list.

⚠️ Interview Pitfalls & Follow-ups

  • Using floating-point arrival times: dist / speed can compare wrongly; the integer ceiling is exact.
  • Killing the farthest monster first: the soonest arrivals must be killed first, which the sort ensures.
  • Off-by-one on the arrival condition: the i-th killed monster (0-indexed) is killed at minute i, so t <= i means it arrived in time.
  • Forgetting that all monsters may be eliminated: return n when the loop completes.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Greedy Problems