LeetCode 1921 - Eliminate Maximum Number of Monsters

LeetCode Problem 1921

Difficulty: 🟡 Medium
Topics: Array, Greedy, Sorting

Solution

Problem Understanding

This problem asks us to determine how many monsters we can eliminate before any one of them reaches the city.

Each monster starts at some distance from the city and moves toward it at a constant speed. We are also given a weapon that can eliminate exactly one monster every minute. The weapon starts fully charged at time 0, which means we may eliminate one monster immediately before any movement occurs.

The important detail is the losing condition:

• If a monster reaches the city exactly when the weapon becomes available again, we still lose before firing.
• That means a monster arriving at time t must already be eliminated before minute t begins.

The input consists of two arrays:

• dist[i] represents the starting distance of monster i
• speed[i] represents how fast monster i moves

For each monster, we can compute the exact time at which it reaches the city:

$$\text{arrival time} = \frac{\text{dist}[i]}{\text{speed}[i]}$$

Since we can eliminate only one monster per minute, the key question becomes:

Can we schedule eliminations so that every monster is destroyed before its arrival time?

The constraints are important:

• n can be as large as 10^5
• A quadratic simulation is too slow
• We need an algorithm around O(n log n) or better

A few edge cases immediately stand out:

• Multiple monsters may arrive at the same minute
• A monster may arrive before minute 1, forcing us to eliminate it immediately
• Some monsters may reach the city exactly when the weapon recharges, which still counts as failure
• All monsters may be eliminable if their arrival times are sufficiently spread apart

The problem guarantees:

• All distances and speeds are positive integers
• The arrays have equal length
• There is at least one monster

Approaches

Brute Force Approach

A straightforward approach would be to simulate the game minute by minute.

At each minute:

1. Compute the remaining distance for every alive monster
2. Check whether any monster has already reached the city
3. Choose one monster to eliminate
4. Advance time by one minute

To maximize survival, we would likely eliminate the monster that reaches the city first.

Although this produces the correct answer, it is inefficient because every minute requires scanning all remaining monsters. In the worst case, this leads to repeated recalculations of positions and arrival priorities.

With up to 10^5 monsters, repeatedly updating monster states becomes too expensive.

Key Insight

The crucial observation is that the actual movement simulation is unnecessary.

A monster is completely characterized by one value:

$$\text{arrival minute} = \frac{\text{dist}[i]}{\text{speed}[i]}$$

We do not care where the monster is at intermediate times. We only care about when it reaches the city.

If we sort monsters by arrival time, then the optimal strategy becomes obvious:

• Always eliminate the monster that arrives earliest

Suppose the sorted arrival times are:

$$t_0 \le t_1 \le t_2 \le \dots$$

At minute 0, we eliminate the first monster.

At minute 1, we eliminate the second monster.

At minute 2, we eliminate the third monster.

For the monster scheduled at minute i, we must have:

$$t_i > i$$

If t_i <= i, that monster reaches the city before or exactly when we can fire again, so we lose.

This transforms the problem into a simple greedy scheduling problem.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Simulates monster movement minute by minute
Optimal	O(n log n)	O(n)	Sort arrival times and greedily eliminate earliest arrivals first

Algorithm Walkthrough

1. Create an array to store each monster's arrival time.

For monster i, the arrival time is:

$$\frac{\text{dist}[i]}{\text{speed}[i]}$$

Instead of using floating point values, we can compute the ceiling minute directly:

$$\left\lceil \frac{\text{dist}[i]}{\text{speed}[i]} \right\rceil$$

In integer arithmetic:

$$\frac{\text{dist}[i] + \text{speed}[i] - 1}{\text{speed}[i]}$$

This tells us the first minute at which the monster reaches the city. 2. Sort the arrival times in ascending order.

This ensures we always consider the most urgent monsters first. 3. Iterate through the sorted arrival times.

At minute i, we attempt to eliminate the ith monster in sorted order. 4. Check whether the current monster arrives too early.

If:

$$\text{arrivalTime}[i] \le i$$

then the monster reaches the city before or exactly when the weapon becomes available.

We immediately return i, since we successfully eliminated exactly i monsters before losing. 5. If all monsters pass the check, return n.

This means every monster can be eliminated before reaching the city.

Why it works

Sorting by arrival time guarantees we always handle the most urgent monster first. If a monster with an earlier arrival time were postponed while a later monster was eliminated first, the earlier monster could reach the city unnecessarily early.

The invariant is:

• After eliminating i monsters, all remaining monsters must arrive strictly after minute i.

If this condition ever fails, no alternative ordering could save us because every remaining monster arrives no later than the current one.

Therefore, the greedy strategy is optimal.

Python Solution

from typing import List

class Solution:
    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:
        arrival_times = []

        for d, s in zip(dist, speed):
            minute = (d + s - 1) // s
            arrival_times.append(minute)

        arrival_times.sort()

        for minute, arrival in enumerate(arrival_times):
            if arrival <= minute:
                return minute

        return len(dist)

The implementation begins by computing the arrival minute for every monster. The expression:

(d + s - 1) // s

computes the ceiling of d / s using integer arithmetic, avoiding floating point precision issues.

After collecting all arrival times, the algorithm sorts them in ascending order. This ensures the monsters that reach the city earliest are handled first.

The loop:

for minute, arrival in enumerate(arrival_times):

represents the firing schedule. At minute 0, we eliminate the first monster. At minute 1, we eliminate the second, and so on.

The condition:

if arrival <= minute:

detects failure. If the monster arrives at or before the current minute, it reaches the city before we can fire.

If the loop finishes successfully, all monsters are eliminated, so the function returns the total number of monsters.

Go Solution

package main

import "sort"

func eliminateMaximum(dist []int, speed []int) int {
	n := len(dist)

	arrivalTimes := make([]int, n)

	for i := 0; i < n; i++ {
		arrivalTimes[i] = (dist[i] + speed[i] - 1) / speed[i]
	}

	sort.Ints(arrivalTimes)

	for minute, arrival := range arrivalTimes {
		if arrival <= minute {
			return minute
		}
	}

	return n
}

The Go solution follows the same logic as the Python implementation.

A slice is used to store arrival times, and sort.Ints sorts them efficiently.

Integer division in Go naturally truncates toward zero, so the ceiling formula:

(dist[i] + speed[i] - 1) / speed[i]

works exactly as intended.

Since all constraints fit comfortably within standard integer ranges, no special overflow handling is required.

Worked Examples

Example 1

dist = [1,3,4]
speed = [1,1,1]

First compute arrival times:

Monster	Distance	Speed	Arrival Time
0	1	1	1
1	3	1	3
2	4	1	4

Sorted arrival times:

[1, 3, 4]

Now simulate eliminations:

Minute	Monster Arrival	Condition	Result
0	1	1 > 0	Eliminate
1	3	3 > 1	Eliminate
2	4	4 > 2	Eliminate

All monsters are eliminated.

Answer:

3

Example 2

dist = [1,1,2,3]
speed = [1,1,1,1]

Arrival times:

Monster	Distance	Speed	Arrival Time
0	1	1	1
1	1	1	1
2	2	1	2
3	3	1	3

Sorted:

[1, 1, 2, 3]

Simulation:

Minute	Monster Arrival	Condition	Result
0	1	1 > 0	Eliminate
1	1	1 <= 1	Lose

We eliminate only one monster before losing.

Answer:

1

Example 3

dist = [3,2,4]
speed = [5,3,2]

Arrival times:

Monster	Distance	Speed	Arrival Time
0	3	5	1
1	2	3	1
2	4	2	2

Sorted:

[1, 1, 2]

Simulation:

Minute	Monster Arrival	Condition	Result
0	1	1 > 0	Eliminate
1	1	1 <= 1	Lose

Answer:

1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting the arrival times dominates the runtime
Space	O(n)	Additional array used to store arrival times

The algorithm performs three major operations:

1. Computing arrival times, which takes O(n)
2. Sorting the array, which takes O(n log n)
3. Scanning the sorted array once, which takes O(n)

The sorting step dominates overall complexity.

The extra space comes from storing the arrival times separately from the input arrays.

Test Cases

solution = Solution()

# Provided examples
assert solution.eliminateMaximum([1, 3, 4], [1, 1, 1]) == 3  # all monsters eliminated
assert solution.eliminateMaximum([1, 1, 2, 3], [1, 1, 1, 1]) == 1  # simultaneous arrival
assert solution.eliminateMaximum([3, 2, 4], [5, 3, 2]) == 1  # fast monsters

# Single monster
assert solution.eliminateMaximum([10], [1]) == 1  # trivial single monster

# Monster reaches immediately after first minute
assert solution.eliminateMaximum([1, 2, 3], [1, 1, 1]) == 3  # enough time for all

# Multiple monsters arriving together
assert solution.eliminateMaximum([2, 2, 2], [1, 1, 1]) == 2  # third monster arrives too early

# Already impossible after first elimination
assert solution.eliminateMaximum([1, 1], [1, 1]) == 1  # second arrives at minute 1

# Large distances
assert solution.eliminateMaximum([100000, 99999], [1, 1]) == 2  # very late arrivals

# Different speeds
assert solution.eliminateMaximum([4, 2, 8], [2, 1, 4]) == 3  # mixed arrival times

# Tight boundary condition
assert solution.eliminateMaximum([2, 3, 4], [1, 1, 1]) == 3  # exact safe ordering

# Monster arriving exactly at firing time
assert solution.eliminateMaximum([1, 2], [1, 2]) == 1  # equality causes loss

Test Summary

Test	Why
[1,3,4]	Verifies normal successful elimination
[1,1,2,3]	Verifies simultaneous arrivals
[3,2,4]	Verifies fast monsters arriving early
Single monster	Smallest valid input
[1,2,3]	Verifies all monsters can survive sequential scheduling
[2,2,2]	Verifies repeated identical arrival times
[1,1]	Verifies immediate unavoidable loss
Large distances	Verifies large values and no overflow issues
Mixed speeds	Verifies varied timing calculations
Exact boundary case	Verifies strict inequality handling
Equality arrival case	Verifies losing when arrival equals firing time

Edge Cases

Multiple Monsters Arriving at the Same Time

One of the easiest mistakes is mishandling monsters that share the same arrival minute.

For example:

dist = [1,1,1]
speed = [1,1,1]

All monsters arrive at minute 1. We can eliminate only one at minute 0, then the remaining monsters reach the city before the weapon recharges.

The implementation handles this correctly because sorted arrival times become:

[1,1,1]

At minute 1, the condition:

arrival <= minute

detects failure immediately.

Monster Arriving Exactly When the Weapon Recharges

The problem explicitly states that this still counts as a loss.

For example:

dist = [1,2]
speed = [1,2]

Arrival times are:

[1,1]

The second monster reaches the city exactly at minute 1, when the weapon becomes available again. Since the game ends before firing, we lose.

This is why the algorithm uses:

arrival <= minute

instead of:

arrival < minute

That equality check is critical.

Very Large Input Size

With 10^5 monsters, inefficient simulations become too slow.

A naive approach that repeatedly updates monster positions could take quadratic time.

The implementation avoids this entirely by converting each monster into a single arrival time and sorting once. This ensures the algorithm remains efficient even at maximum constraints.