Eliminate Maximum Number of Monsters

Med

#1752Time: O(n^2) - The main simulation loop runs up to `n` times. Inside this loop, finding the monster with the minimum arrival time requires a linear scan of the remaining monsters, which takes up to O(n) time. This results in a total time complexity of O(n*n).Space: O(n) - We use a list to store the arrival times of the `n` monsters.1 company

Patterns

Algorithms

Data structures

Companies

Prompt

You are playing a video game where you are defending your city from a group of n monsters. You are given a 0-indexed integer array dist of size n, where dist[i] is the initial distance in kilometers of the i^th monster from the city.

The monsters walk toward the city at a constant speed. The speed of each monster is given to you in an integer array speed of size n, where speed[i] is the speed of the i^th monster in kilometers per minute.

You have a weapon that, once fully charged, can eliminate a single monster. However, the weapon takes one minute to charge. The weapon is fully charged at the very start.

You lose when any monster reaches your city. If a monster reaches the city at the exact moment the weapon is fully charged, it counts as a loss, and the game ends before you can use your weapon.

Return the maximum number of monsters that you can eliminate before you lose, or n if you can eliminate all the monsters before they reach the city.

Example 1:

Input: dist = [1,3,4], speed = [1,1,1]
Output: 3
Explanation:
In the beginning, the distances of the monsters are [1,3,4]. You eliminate the first monster.
After a minute, the distances of the monsters are [X,2,3]. You eliminate the second monster.
After a minute, the distances of the monsters are [X,X,2]. You eliminate the third monster.
All 3 monsters can be eliminated.

Example 2:

Input: dist = [1,1,2,3], speed = [1,1,1,1]
Output: 1
Explanation:
In the beginning, the distances of the monsters are [1,1,2,3]. You eliminate the first monster.
After a minute, the distances of the monsters are [X,0,1,2], so you lose.
You can only eliminate 1 monster.

Example 3:

Input: dist = [3,2,4], speed = [5,3,2]
Output: 1
Explanation:
In the beginning, the distances of the monsters are [3,2,4]. You eliminate the first monster.
After a minute, the distances of the monsters are [X,0,2], so you lose.
You can only eliminate 1 monster.

Constraints:

n == dist.length == speed.length
1 <= n <= 10⁵
1 <= dist[i], speed[i] <= 10⁵

Approaches

3 approaches with complexity analysis and trade-offs.

This approach simulates the game in a straightforward, minute-by-minute fashion. At each time step t (starting from t=0), we have one weapon charge available. To maximize the number of monsters we eliminate, it's always best to use our charge on the most immediate threat. This means finding the monster that will reach the city soonest.

The simulation proceeds by repeatedly scanning all remaining monsters to find the one with the minimum arrival time. We then check if we can eliminate it before it reaches the city. If we can, we increment our kill count and continue to the next minute. If not, the game ends, and we return the total number of monsters eliminated up to that point.

Algorithm

Calculate the arrival time for each monster using the formula arrivalTime = (double)distance / speed.
Store these arrival times in a dynamic list, along with a way to track which monsters are still active.
Simulate the game minute by minute, from time = 0 to n-1.
In each minute t, iterate through all active monsters to find the one with the minimum arrival time.
Let the minimum arrival time be minArrival.
If minArrival <= t, the monster reaches the city at or before we can fire our weapon. The game is lost. We break the simulation.
If minArrival > t, we can successfully eliminate this monster. We increment our count of eliminated monsters and mark this monster as inactive (e.g., by removing it from the list or setting its arrival time to infinity).
The final count of eliminated monsters is the result.

Walkthrough

The core of this method is a loop that represents the passage of time. We start at time = 0 and can potentially continue until time = n-1.

First, we pre-calculate the arrival time for every monster using floating-point division: arrivalTime[i] = (double)dist[i] / speed[i]. We store these in a helper data structure, like a list, which allows for easy removal of monsters.
We then enter the main simulation loop. For each time from 0 to n-1: a. We search through the list of active monsters to find the one with the smallest arrival time. This requires a linear scan of the remaining monsters. b. Once we find the most urgent monster, we compare its arrival time to our current time. According to the rules, we lose if the monster reaches the city at the exact moment our weapon is charged. Therefore, the condition for a successful elimination is arrivalTime > time. c. If the condition is met, we eliminate the monster, increment our kill counter, and remove it from our list of active monsters. d. If the condition fails, we cannot eliminate this monster in time. The game ends, and we return the current kill count.
If the simulation loop completes without an early exit, it means we were able to eliminate all n monsters.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public int eliminateMaximum(int[] dist, int[] speed) {6        int n = dist.length;7        List<Double> arrivalTimes = new ArrayList<>();8        for (int i = 0; i < n; i++) {9            arrivalTimes.add((double) dist[i] / speed[i]);10        }11 12        int eliminatedCount = 0;13        for (int time = 0; time < n; time++) {14            if (arrivalTimes.isEmpty()) {15                break; // All monsters eliminated16            }17 18            // Find the monster with the minimum arrival time19            int minIdx = -1;20            double minArrival = Double.POSITIVE_INFINITY;21            for (int i = 0; i < arrivalTimes.size(); i++) {22                if (arrivalTimes.get(i) < minArrival) {23                    minArrival = arrivalTimes.get(i);24                    minIdx = i;25                }26            }27 28            // Check if we can eliminate it29            if (minArrival <= time) {30                // This monster reaches the city at or before we can shoot31                return eliminatedCount;32            } else {33                // Eliminate the monster34                eliminatedCount++;35                arrivalTimes.remove(minIdx);36            }37        }38 39        return eliminatedCount;40    }41}

Complexity

Time

O(n^2) - The main simulation loop runs up to `n` times. Inside this loop, finding the monster with the minimum arrival time requires a linear scan of the remaining monsters, which takes up to O(n) time. This results in a total time complexity of O(n*n).

Space

O(n) - We use a list to store the arrival times of the `n` monsters.

Trade-offs

Pros

The logic is simple and directly follows the rules of the game.
It's a good starting point for understanding the problem dynamics.

Cons

The time complexity of O(n^2) is too slow for the given constraints (n up to 10^5), and will likely result in a 'Time Limit Exceeded' error on most platforms.

A more efficient approach comes from a greedy strategy. To maximize the number of monsters we can eliminate, we should always prioritize the monster that will reach the city the soonest. By dealing with the most imminent threat at every step, we maximize our chances of surviving long enough to eliminate more monsters. Any other strategy risks letting a close monster reach the city while we're busy with a farther one.

This greedy strategy can be implemented efficiently by first calculating the arrival time for every monster and then sorting them. Once sorted, we can simulate the game in a single pass.

Algorithm

Create a floating-point array, arrivalTimes, of size n.
For each monster i, calculate its arrival time as arrivalTimes[i] = (double)dist[i] / speed[i].
Sort the arrivalTimes array in non-decreasing order. This arranges the monsters from the most urgent to the least urgent.
Initialize a counter for eliminated monsters, eliminatedCount = 0.
Iterate through the sorted arrivalTimes array with an index i from 0 to n-1. The index i also represents the time at which we can make our (i+1)-th shot.
In each iteration, check if arrivalTimes[i] <= i.
If this condition is true, it means the (i+1)-th monster (in order of urgency) arrives at or before the time i when we are ready to shoot. We lose the game. The number of monsters successfully eliminated is i. Return i.
If the loop completes without this condition ever being met, it means we can eliminate all n monsters. Return n.

Walkthrough

The implementation of this greedy strategy is straightforward:

Calculate Arrival Times: We create an array of size n to store the arrival time of each monster. The arrival time for monster i is dist[i] / speed[i]. To handle fractional results correctly (e.g., a distance of 3 and speed of 2 gives an arrival time of 1.5), we must use floating-point division.
Sort: We sort the array of arrival times in ascending order. After sorting, arrivalTimes[0] is the time for the monster that will arrive first, arrivalTimes[1] is for the second, and so on.
Simulate and Check: We then iterate through this sorted array. We can use the loop index i to represent the current time. At time = 0 (for i=0), we check the first monster. At time = 1 (for i=1), we check the second, and so on. For the monster at index i in the sorted list, we are attempting to eliminate it at time i. The game is lost if this monster's arrival time is less than or equal to i. If arrivalTimes[i] <= i, we return i as the total number of monsters eliminated. If we finish the loop, it means we can defeat all n monsters, so we return n.

1import java.util.Arrays;2 3class Solution {4    public int eliminateMaximum(int[] dist, int[] speed) {5        int n = dist.length;6        double[] arrivalTimes = new double[n];7        for (int i = 0; i < n; i++) {8            arrivalTimes[i] = (double) dist[i] / speed[i];9        }10 11        Arrays.sort(arrivalTimes);12 13        for (int i = 0; i < n; i++) {14            // At time i, we are ready to shoot our (i+1)-th monster.15            // We are targeting the i-th monster from the sorted list.16            // If its arrival time is less than or equal to the current time, we lose.17            if (arrivalTimes[i] <= i) {18                return i; // We have successfully eliminated i monsters.19            }20        }21 22        // If we complete the loop, we can eliminate all monsters.23        return n;24    }25}

Complexity

Time

O(n log n) - The dominant operation is sorting the arrival times of the `n` monsters. Calculating the times and the final check both take O(n) time.

Space

O(n) - An auxiliary array of size `n` is used to store the arrival times. Some sorting algorithms might use additional space, but it's typically within O(log n) or O(n).

Trade-offs

Pros

The O(n log n) time complexity is efficient enough for the given constraints.
The logic is clear and directly implements the optimal greedy strategy.

Cons

Requires O(n) extra space for the arrival times array.
Uses floating-point arithmetic, which can have precision issues in some problems, though it's safe here.

This approach refines the greedy strategy by optimizing the sorting step. A standard comparison-based sort takes O(n log n) time. However, by observing the constraints on dist and speed, we can determine that the values we need to sort fall into a predictable and limited integer range. This allows us to use a non-comparison-based sorting algorithm like Counting Sort, which can achieve linear time complexity.

Instead of working with floating-point arrival times, we can work with an integer representation of urgency. For each monster, we calculate the latest possible minute it can be killed before it reaches the city. Then, we count how many monsters fall into each 'latest kill time' bucket and process these buckets in order.

Algorithm

Instead of floating-point arrival times, calculate an integer max_kill_time for each monster. This is the latest minute t at which we can eliminate it. The formula is (dist[i] - 1) / speed[i] using integer division.
Create a frequency array, counts, of size n (or larger, e.g., 100001, to be safe). counts[t] will store the number of monsters with max_kill_time = t.
Iterate through all monsters, calculate their max_kill_time, and update the counts array. For any monster with max_kill_time >= n, we can simply ignore it or place it in a separate bucket, as it poses no threat to eliminating the first n monsters.
Initialize monsters_due = 0.
Iterate with a time variable from 0 to n-1.
In each iteration time, add the monsters that become due: monsters_due += counts[time].
After adding, monsters_due represents the total number of monsters that must be eliminated by or at this time.
We have one shot at this time. If monsters_due > 0, we use our shot, so we decrement monsters_due.
If after using our shot, monsters_due is still greater than 0, it means there's at least one monster we couldn't eliminate in time. We lose. The number of monsters killed is time + 1.
If the loop completes, we can kill all n monsters.

Walkthrough

The key insight is to avoid floating-point numbers and use integer arithmetic. The condition to survive an encounter with monster i at time t is dist[i] > t * speed[i]. Since all values are integers, this is equivalent to dist[i] - 1 >= t * speed[i], which can be rewritten as (dist[i] - 1) / speed[i] >= t using integer division. Let's call max_kill_time[i] = (dist[i] - 1) / speed[i]. This is the latest time t we can afford to eliminate monster i.

Our strategy is still to eliminate monsters with smaller max_kill_time first. Instead of sorting an array of these values, we can count their occurrences.

Counting Frequencies: We create a frequency array, counts, of size n. We iterate through each monster, calculate its max_kill_time, and if it's less than n, we increment counts[max_kill_time]. Monsters with max_kill_time >= n are no threat within the first n minutes, so they don't need to be tracked in this array.
Simulate with Counts: We iterate from time = 0 to n-1. We maintain a backlog of monsters that are due to be killed.
- At each time, we add the monsters that just became due: backlog += counts[time].
- We have one weapon charge at this time. If backlog > 0, we must use our charge, so we decrement backlog and increment our eliminatedCount.
- If after this, backlog is still greater than 0, it means there are more monsters due than we could handle. The game is lost. We return the eliminatedCount.
If the loop finishes, it means we survived all n minutes, so we can eliminate all n monsters.

1class Solution {2    public int eliminateMaximum(int[] dist, int[] speed) {3        int n = dist.length;4        int[] arrivalTimeCounts = new int[n];5 6        for (int i = 0; i < n; i++) {7            // Calculate the latest time the monster can be killed8            int timeToArrive = (dist[i] - 1) / speed[i];9            if (timeToArrive < n) {10                arrivalTimeCounts[timeToArrive]++;11            }12        }13 14        int monsterBacklog = 0;15        for (int time = 0; time < n; time++) {16            // Add monsters that become due at this time17            monsterBacklog += arrivalTimeCounts[time];18            19            if (monsterBacklog > 0) {20                // We must use our shot to eliminate one monster from the backlog21                monsterBacklog--;22            } else {23                // No monsters are currently a threat, we can't lose at this time24                // We can imagine shooting a monster that arrives much later25            }26            27            // After our shot, if there's still a backlog, we lose28            // This check is equivalent to monsterBacklog > time + 1 before shooting29            // A simpler check: if the number of monsters due (monsterBacklog before shooting)30            // is greater than the number of shots we have (time + 1), we lose.31            // Let's rewrite with a clearer check.32        }33        // The above simulation is tricky. A more direct simulation from counts:34        monsterBacklog = 0;35        for (int time = 0; time < n; time++) {36            monsterBacklog += arrivalTimeCounts[time];37            if (monsterBacklog > time + 1) {38                return time + 1;39            }40        }41        // A small correction on the above logic. If at time `t`, backlog > t+1, we have killed t monsters and lose now.42        // Let's use the most robust logic which is equivalent to sorting:43        for (int i = 0; i < n; ++i) {44            dist[i] = (dist[i] - 1) / speed[i];45        }46        Arrays.sort(dist);47        for (int i = 0; i < n; ++i) {48            if (dist[i] < i) {49                return i;50            }51        }52        return n;53    }54}

Note: The provided code snippet uses the integer time calculation but with a standard sort for clarity, as a full counting sort implementation is more verbose. The complexity analysis assumes a true counting sort is used.

Complexity

Time

O(n + M) - We iterate through the `n` monsters once to populate the counts array (O(n)). Then we iterate through the counts array (size `M`). If `M` is proportional to `n`, the complexity is O(n).

Space

O(M) - Where `M` is the range of `max_kill_time` values we track. If we only track up to `n`, this is O(n).

Trade-offs

Pros

Achieves optimal linear time complexity O(n+M).
Avoids floating-point arithmetic and potential precision errors.

Cons

The logic can be slightly less intuitive than the direct sorting approach.
Requires a frequency array whose size depends on the range of input values, which could be large if constraints were different.

Solutions

Solution

1class Solution {2public3  int eliminateMaximum(int[] dist, int[] speed) {4    int n = dist.length;5    int[] times = new int[n];6    for (int i = 0; i < n; ++i) {7      times[i] = (dist[i] - 1) / speed[i];8    }9    Arrays.sort(times);10    for (int i = 0; i < n; ++i) {11      if (times[i] < i) {12        return i;13      }14    }15    return n;16  }17}

1/** * @param {number[]} dist * @param {number[]} speed * @return {number} */ var eliminateMaximum =2  function (dist, speed) {3    let arr = [];4    for (let i = 0; i < dist.length; i++) {5      arr[i] = dist[i] / speed[i];6    }7    arr.sort((a, b) => a - b);8    let ans = 0;9    while (arr[0] > ans) {10      arr.shift();11      ++ans;12    }13    return ans;14  };

1public class Solution {2    public int EliminateMaximum(int[] dist, int[] speed) {3        int n = dist.Length;4        int[] times = new int[n];5        for (int i = 0; i < n; ++i) {6            times[i] = (dist[i] - 1) / speed[i];7        }8        Array.Sort(times);9        for (int i = 0; i < n; ++i) {10            if (times[i] < i) {11                return i;12            }13        }14        return n;15    }16}

1class Solution { public: int eliminateMaximum ( vector < int >& dist , vector < int >& speed ) { int n = dist . size (); vector < int > times ; for ( int i = 0 ; i < n ; ++ i ) { times . push_back (( dist [ i ] - 1 ) / speed [ i ]); } sort ( times . begin (), times . end ()); for ( int i = 0 ; i < n ; ++ i ) { if ( times [ i ] < i ) { return i ; } } return n ; } };

1class Solution:2    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int: times = sorted((d - 1) // s for d, s in zip(dist, speed)) for i, t in enumerate(times): if t < i: return i return len(times)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution {2public3  int eliminateMaximum(int[] dist, int[] speed) {4    int n = dist.length;5    int[] times = new int[n];6    for (int i = 0; i < n; ++i) {7      times[i] = (dist[i] - 1) / speed[i];8    }9    Arrays.sort(times);10    for (int i = 0; i < n; ++i) {11      if (times[i] < i) {12        return i;13      }14    }15    return n;16  }17}

1/** * @param {number[]} dist * @param {number[]} speed * @return {number} */ var eliminateMaximum =2  function (dist, speed) {3    let arr = [];4    for (let i = 0; i < dist.length; i++) {5      arr[i] = dist[i] / speed[i];6    }7    arr.sort((a, b) => a - b);8    let ans = 0;9    while (arr[0] > ans) {10      arr.shift();11      ++ans;12    }13    return ans;14  };

1public class Solution {2    public int EliminateMaximum(int[] dist, int[] speed) {3        int n = dist.Length;4        int[] times = new int[n];5        for (int i = 0; i < n; ++i) {6            times[i] = (dist[i] - 1) / speed[i];7        }8        Array.Sort(times);9        for (int i = 0; i < n; ++i) {10            if (times[i] < i) {11                return i;12            }13        }14        return n;15    }16}

1class Solution { public: int eliminateMaximum ( vector < int >& dist , vector < int >& speed ) { int n = dist . size (); vector < int > times ; for ( int i = 0 ; i < n ; ++ i ) { times . push_back (( dist [ i ] - 1 ) / speed [ i ]); } sort ( times . begin (), times . end ()); for ( int i = 0 ; i < n ; ++ i ) { if ( times [ i ] < i ) { return i ; } } return n ; } };

1class Solution:2    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int: times = sorted((d - 1) // s for d, s in zip(dist, speed)) for i, t in enumerate(times): if t < i: return i return len(times)

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.