Eliminate Maximum Number of Monsters: Greedy with Sorted Arrival Times

Eliminate Maximum Number of Monsters (LeetCode 1921) is a greedy problem disguised as a simulation. You have a city under attack by monsters. Each monster starts at some distance and moves toward you at a constant speed. You have a weapon that fires once per minute, starting at minute 0, and each shot eliminates exactly one monster. Your goal: maximize the number of monsters you eliminate before any of them reaches the city.

The brute force instinct is to simulate every minute, track each monster's position, and decide which to target. But there is a much cleaner way to think about it.

The problem

You are given two arrays dist and speed, both of length n. Monster i starts at distance dist[i] and moves toward the city at speed[i] units per minute. Your weapon is charged at minute 0 and takes one full minute to recharge after each shot. Each shot eliminates one monster. Return the maximum number of monsters you can eliminate before any monster reaches the city (distance 0).

The key question is: which monster should you shoot first? If you pick the wrong order, a closer monster might slip through while you are busy targeting one that is farther away.

Why arrival times are the key

Instead of tracking positions over time, compute when each monster will arrive at the city. Monster i arrives at minute ceil(dist[i] / speed[i]). Once you have these arrival times, the original distances and speeds do not matter anymore. The problem reduces to: given a list of deadlines, can you process one per minute (starting at minute 0) before each deadline passes?

This is the classic greedy insight. Sort the arrival times in ascending order, then fire at the closest monster first. If at minute i the monster you are targeting has already arrived (its arrival time is i or less), you lose. Otherwise, you eliminate it and move to the next.

Why is greedy optimal here? If you skip a monster that arrives sooner to target one that arrives later, the earlier monster will reach the city before you get another chance to fire. By always targeting the most urgent threat, you never waste a shot on a monster that could have waited.

The algorithm

1. Compute arrival times: arrival[i] = ceil(dist[i] / speed[i]) for each monster.
2. Sort the arrival times in ascending order.
3. Iterate through the sorted array. At index i (minute i), check if arrival[i] > i. If yes, eliminate it. If no, the monster has reached the city and you stop.
4. Return the count of eliminated monsters.

import math

def eliminateMaximum(dist: list[int], speed: list[int]) -> int:
    arrivals = sorted(math.ceil(d / s) for d, s in zip(dist, speed))

    for i, t in enumerate(arrivals):
        if t <= i:
            return i

    return len(dist)

That is the entire solution. One line to compute and sort arrival times, then a single pass to count how many you can eliminate.

Step-by-step walkthrough

Let's trace through a more interesting example where you cannot eliminate all monsters. Consider dist = [1, 3, 4, 3, 2] and speed = [1, 1, 1, 1, 1].

First, compute arrival times: ceil(1/1) = 1, ceil(3/1) = 3, ceil(4/1) = 4, ceil(3/1) = 3, ceil(2/1) = 2. That gives [1, 3, 4, 3, 2]. After sorting: [1, 2, 3, 3, 4].

Now walk through each minute:

The greedy approach correctly identifies that two monsters with the same arrival time create a bottleneck. You can only kill one per minute, so when two monsters both arrive at minute 3, you can handle the first but not the second.

Why ceil instead of regular division

Monster i reaches the city when it has traveled dist[i] units at speed[i] units per minute. The arrival time is dist[i] / speed[i], but since we measure in whole minutes and the monster arrives the moment it covers the full distance, we need the ceiling. A monster at distance 5 with speed 2 arrives at ceil(5/2) = 3 minutes, not 2.5.

In Python, math.ceil(d / s) handles this. You can also use the integer arithmetic trick (d + s - 1) // s to avoid floating point.

Complexity analysis

The sort takes O(n log n). Computing arrival times is O(n). The greedy scan is O(n). Total: O(n log n). Space is O(n) for the arrival times array.

Edge cases to watch for

• All monsters arrive at minute 1. You fire at minute 0 and eliminate one. At minute 1, the rest arrive simultaneously. Answer: 1.
• One monster. You always eliminate it at minute 0 (since arrival >= 1 for any positive distance and speed). Answer: 1.
• All monsters can be eliminated. If every arrival[i] > i after sorting, you eliminate all of them. Return n.
• A monster at distance 0. This does not appear in valid inputs (constraints say dist[i] >= 1), but if it did, you could not eliminate it since it has already arrived.
• Large distance, small speed. Arrival time could be very large, meaning that monster is easy to handle. The sort puts it last, which is correct since it is the least urgent.

The building blocks

Ceiling division

The first step is converting raw distances and speeds into deadlines. This is the same "compute a derived value per element" pattern you see in many array problems. The specific operation here is ceiling division, which shows up whenever you need to figure out how many whole units are required to cover a distance or fill a capacity.

Sort-then-scan greedy

After computing arrival times, you sort and scan. This is the same skeleton as Non-overlapping Intervals (sort by end time, greedily keep compatible intervals) and Task Scheduler (the most frequent task drives the structure). The pattern is:

1. Transform the input into a sortable metric (arrival time, end time, frequency).
2. Sort by that metric.
3. Make a single pass, greedily choosing the locally optimal action at each step.

derived = sorted(transform(x) for x in input)

for i, val in enumerate(derived):
    if not feasible(i, val):
        return i

return len(derived)

This template applies to any problem where you process items one at a time in priority order and stop when a constraint is violated.

From understanding to recall

The logic of this problem is clean: compute arrival times, sort, scan. The part that trips people up is the comparison direction. Is it arrival[i] > i or arrival[i] >= i? Think about it this way: you fire at minute i. If the monster arrives at minute i (meaning arrival[i] == i), it has already reached the city by the time you fire. So you need arrival[i] to be strictly greater than i. The check arrival[i] <= i is the failure condition.

The other detail worth locking in is ceiling division. You need ceil(dist/speed), not floor. A monster 5 units away at speed 2 arrives at minute 3, not minute 2. Getting this wrong changes your arrival times and gives the wrong answer.

Spaced repetition helps you internalize both of these details. After a few reps at increasing intervals, "compute ceil, sort, scan for deadline violations" becomes automatic. No more second-guessing the comparison or the division.

Related posts

• Non-overlapping Intervals - Another greedy problem where sorting by a derived metric (end time) and scanning in order gives the optimal solution
• Task Scheduler - Greedy scheduling where the most constrained element drives the solution structure
• Merge Intervals - The foundational sort-and-sweep interval problem that builds the same pattern intuition