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
- Monster
iarrives afterceil(dist[i] / speed[i])minutes. - You kill one monster per minute, starting at minute 0, so the
i-th killed monster (0-indexed) is killed at minutei. - Sort the arrival times; kill the soonest arrivals first.
- If the
i-th soonest arrival is at or before minutei, it has already reached the city, so you have eliminatedimonsters.
💻 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 / speedcan 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 minutei, sot <= imeans it arrived in time. - Forgetting that all monsters may be eliminated: return
nwhen 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.