Watch 10 video solutions for Eliminate Maximum Number of Monsters, a medium level problem involving Array, Greedy, Sorting. This walkthrough by NeetCode has 9,461 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |