Skip to main content
Talentd

Eliminate Maximum Number of Monsters - Solution & Explanation

MediumArrayGreedySorting16 min readAsked at: Meta, Google, Agoda
Practice this problem

Problem Statement

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.length
  • 1 <= n <= 105
  • 1 <= dist[i], speed[i] <= 105

Approach Overview

Problem 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 1: Calculate Arrival Times and Eliminate in Order

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to sorting the times.
Space Complexity: O(n) to store the arrival times.

Try this approach in the editor →

Approach 2: Binary Search Optimization with Sorted Distances

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.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(n log n) due to the sort operation.
Space Complexity: O(n) to store arrival times.

Try this approach in the editor →

Approach 3: Sorting + Greedy

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.

Code

PythonJavaC++GoTypeScriptJavaScriptC

Python

Java

C++

Go

TypeScript

JavaScript

C

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Calculate Arrival Times and Eliminate in Order

Time Complexity: O(n log n) due to sorting the times.
Space Complexity: O(n) to store the arrival times.

Binary Search Optimization with Sorted Distances

Time Complexity: O(n log n) due to the sort operation.
Space Complexity: O(n) to store arrival times.

Sorting + Greedy—

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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 TimesO(n log n)O(n)Useful when framing the problem as a feasibility check for k eliminations.

Video Solution

Eliminate Maximum Number of Monsters - Leetcode 1921 - Weekly Contest 248 - Python • NeetCode • 9,644 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Eliminate Maximum Number of Monsters easy or hard?
LeetCode classifies this problem as Medium difficulty. The challenge lies in recognizing that each monster creates a deadline based on distance and speed. Once converted to arrival times, the problem reduces to a straightforward greedy scheduling check.
Eliminate Maximum Number of Monsters Python/Java solution
Most implementations compute arrival times using integer math like (dist[i] - 1) // speed[i] + 1 to simulate ceiling division. The times are sorted and then iterated while checking whether arrival[i] > i. This pattern works identically in Python, Java, C++, and JavaScript.
How to solve Eliminate Maximum Number of Monsters in O(n)?
A strict O(n) solution is difficult because ordering monsters by arrival time is necessary for the greedy strategy. Most accepted solutions compute arrival times and sort them, leading to O(n log n) complexity. If arrival times fall within a small bounded range, counting or bucket techniques could reduce the sorting cost.
What is the best approach for Eliminate Maximum Number of Monsters?
The most efficient approach converts each monster's distance and speed into an arrival time and sorts those times. A greedy simulation eliminates monsters in order of earliest arrival. If a monster's arrival time is less than or equal to the current minute index, it reaches the city. This solution runs in O(n log n) time due to sorting and uses O(n) space.
Is Eliminate Maximum Number of Monsters asked at Google/Amazon/Meta?
Problems combining greedy scheduling and arrival-time calculations frequently appear in interviews at large tech companies such as Amazon, Google, and Meta. This question tests reasoning about deadlines, sorting strategies, and simulation logic rather than complex data structures.
What data structure is used in Eliminate Maximum Number of Monsters?
The solution primarily uses arrays to store computed arrival times. Sorting the array allows a greedy elimination order. No advanced data structures are required beyond basic array processing and sorting operations.
What is the time complexity of Eliminate Maximum Number of Monsters?
The optimal solution runs in O(n log n) time. Computing arrival times takes O(n), sorting those times takes O(n log n), and the final elimination simulation takes O(n). Space complexity is O(n) to store the arrival times.

Ready to solve this problem?

Practice Eliminate Maximum Number of Monsters with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Health to Beat Game

Next

Minimum Time to Kill All Monsters