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 ith 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 ith 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.length1 <= n <= 1051 <= dist[i], speed[i] <= 105Problem Overview: You are given two arrays dist and speed describing monsters moving toward a city. Each minute you can eliminate exactly one monster. The goal is to maximize how many monsters you eliminate before any monster reaches the city.
The key observation: each monster has a fixed arrival time at the city. If a monster arrives at time t, you must eliminate it before minute t. Once you convert distance and speed into arrival times, the problem becomes a scheduling task.
Approach 1: Calculate Arrival Times and Eliminate in Order (Greedy + Sorting) (Time: O(n log n), Space: O(n))
Compute each monster’s arrival minute using arrival = ceil(dist[i] / speed[i]). Store these arrival times in an array and sort them. Now simulate the elimination process: at minute i, you eliminate one monster. If the next monster’s arrival time is less than or equal to i, it has already reached the city and the process stops.
This works because eliminating monsters with the earliest arrival deadlines first maximizes survival time. The sorted order effectively implements a greedy scheduling strategy. The algorithm iterates once to compute arrival times, sorts them, and then scans the list to count how many monsters you can eliminate.
This approach relies on simple array processing and ordering operations, making it a natural application of Array, Sorting, and Greedy techniques.
Approach 2: Binary Search Optimization with Sorted Distances (Time: O(n log n), Space: O(n))
Another perspective is to binary search the maximum number of monsters you can eliminate. First compute and sort the arrival times. Then perform a binary search on the answer k (how many monsters you try to eliminate). For a candidate k, verify whether the first k monsters can all be eliminated before their arrival times.
The validation step checks if arrival[i] > i for every monster i in the first k positions. If the condition holds, eliminating k monsters is feasible; otherwise it is not. Binary search narrows the feasible range until the maximum valid value is found.
This method adds an extra algorithmic layer but is useful when thinking about the problem as a feasibility check rather than a direct simulation.
Recommended for interviews: The greedy arrival-time approach is what interviewers expect. Converting distances to arrival deadlines and sorting them shows you recognize the scheduling pattern. The binary search variant demonstrates deeper reasoning about feasibility checks, but the greedy simulation is shorter, clearer, and typically preferred in interviews.
This approach involves computing the exact time each monster will take to reach the city and then eliminating them in the order of their arrival times. The goal is to eliminate as many monsters as possible before any monster reaches the city.
The C solution calculates the time each monster takes to reach the city and sorts these times. It then iterates over the sorted times, using each minute to eliminate the monster that reaches the city next. If at any point the current minute is equal to or greater than the time a monster reaches the city, the process stops.
Time Complexity: O(n log n) due to sorting the times.
Space Complexity: O(n) to store the arrival times.
This approach improves the efficiency of eliminating the maximum number of monsters by using a binary search method. It pre-calculates when a monster will reach the city and uses efficient search techniques to make decisions dynamically during the elimination process.
By using a library function like bisect_right in Python, the code finds the largest index to insert a value (in this case to simulate minutes passing) while maintaining order. This efficiently tells us the maximum monsters that can be eliminated as time progresses.
Python
JavaScript
Time Complexity: O(n log n) due to the sort operation.
Space Complexity: O(n) to store arrival times.
We use the times array to record the latest time each monster can be eliminated. For the i-th monster, the latest time it can be eliminated is:
$times[i] = \left\lfloor \frac{dist[i]-1}{speed[i]} \right\rfloor
Next, we sort the times array in ascending order.
Then, we traverse the times array. For the i-th monster, if times[i] geq i, it means the i-th monster can be eliminated. Otherwise, it means the i-th monster cannot be eliminated, and we return i immediately.
If all monsters can be eliminated, we return n.
The time complexity is O(n times log n), and the space complexity is O(n). Here, n$ is the length of the array.
Python
Java
C++
Go
TypeScript
JavaScript
C
| Approach | Complexity |
|---|---|
| Calculate Arrival Times and Eliminate in Order | Time Complexity: O(n log n) due to sorting the times. |
| Binary Search Optimization with Sorted Distances | Time Complexity: O(n log n) due to the sort operation. |
| Sorting + Greedy | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Calculate Arrival Times and Eliminate in Order (Greedy + Sorting) | O(n log n) | O(n) | Best general solution. Simple simulation after sorting arrival times. |
| Binary Search with Sorted Arrival Times | O(n log n) | O(n) | Useful when framing the problem as a feasibility check for k eliminations. |
Eliminate Maximum Number of Monsters - Leetcode 1921 - Weekly Contest 248 - Python • NeetCode • 9,461 views views
Watch 9 more video solutions →Practice Eliminate Maximum Number of Monsters with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor