Eliminate Maximum Number of Monsters solution and explanation
Google
9 more videos on this problem
Eliminate Maximum Number of Monsters - Leetcode 1921 - Weekly Contest 248 - PythonNeetCode · 8:19 · 9K views
Eliminate Maximum Number of Monsters | Intuition | GOOGLE | META | AMAZON | Leetcode - 1921codestorywithMIK · 20:56 · 6K views
Leetcode Solution : Eliminate Maximum Number of MonstersFraz · 8:08 · 5K views
1921. Eliminate Maximum Number of Monsters | Greedy | Leetcode 1921Aryan Mittal · 12:43 · 1K views
Eliminate Maximum Number of Monsters | 07 Nov Leetcode POTD | Screencast + Video Solutioncpwithcpp · 7:19 · 865 views
Leetcode Weekly Contest 248 | 1921. Eliminate Maximum Number of Monsters(Medium) in EnglishCompetitive Somya · 4:52 · 364 views
Daily Leetcode #1316: Nov 07, 2023 - 1921. Eliminate Maximum Number of MonstersProgramming Live with Larry · 8:35 · 351 views
1921. Eliminate Maximum Number of Monsters (Leetcode Medium)Programming Live with Larry · 14:40 · 221 views
Solving LeetCode 1921 Eliminate Maximum Number of Monsters | Google Interview QuestionCode Harmony · 7:12 · 203 views
LeetCode 1921. Eliminate Maximum Number of MonstersSakura Programming · 4:22 · 143 views
The problem
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] <= 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.
def eliminateMaximum(dist, speed):
time = [(d + s - 1) // s for d, s in zip(dist, speed)] # ceiling of (dist[i] / speed[i])
time.sort()
for i, t in enumerate(time):
if t <= i:
return i
return len(time)
print(eliminateMaximum([1, 3, 4], [1, 1, 1]))import java.util.Arrays;
public class MonsterElimination {
public int eliminateMaximum(int[] dist, int[] speed) {
int n = dist.length;
int[] time = new int[n];
for (int i = 0; i < n; i++) {
time[i] = (dist[i] + speed[i] - 1) / speed[i]; // ceiling of (dist[i] / speed[i])
}
Arrays.sort(time);
for (int i = 0; i < n; i++) {
if (time[i] <= i) {
return i;
}
}
return n;
}
public static void main(String[] args) {
MonsterElimination me = new MonsterElimination();
int[] dist = {1, 3, 4};
int[] speed = {1, 1, 1};
System.out.println(me.eliminateMaximum(dist, speed));
}
}#include <iostream>
#include <vector>
#include <algorithm>
int eliminateMaximum(std::vector<int>& dist, std::vector<int>& speed) {
std::vector<int> time;
for (int i = 0; i < dist.size(); ++i) {
time.push_back((dist[i] + speed[i] - 1) / speed[i]); // ceiling of (dist[i] / speed[i])
}
std::sort(time.begin(), time.end());
for (int i = 0; i < time.size(); ++i) {
if (time[i] <= i) {
return i;
}
}
return time.size();
}
int main() {
std::vector<int> dist = {1, 3, 4};
std::vector<int> speed = {1, 1, 1};
int result = eliminateMaximum(dist, speed);
std::cout << result << std::endl;
return 0;
}function eliminateMaximum(dist, speed) {
let time = dist.map((d, i) => Math.ceil(d / speed[i]));
time.sort((a, b) => a - b);
for (let i = 0; i < time.length; i++) {
if (time[i] <= i) {
return i;
}
}
return time.length;
}
console.log(eliminateMaximum([1, 3, 4], [1, 1, 1]));#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int *)a) - (*(int *)b);
}
int eliminateMaximum(int* dist, int distSize, int* speed, int speedSize){
int time[distSize];
for(int i = 0; i < distSize; i++) {
time[i] = (dist[i] + speed[i] - 1) / speed[i]; // ceiling of (dist[i] / speed[i])
}
qsort(time, distSize, sizeof(int), compare);
for(int i = 0; i < distSize; i++) {
if(time[i] <= i) return i;
}
return distSize;
}
int main() {
int dist[] = {1, 3, 4};
int speed[] = {1, 1, 1};
int result = eliminateMaximum(dist, 3, speed, 3);
printf("%d\n", result);
return 0;
}using System;
using System.Linq;
public class MonsterElimination {
public int EliminateMaximum(int[] dist, int[] speed) {
int n = dist.Length;
int[] time = new int[n];
for (int i = 0; i < n; i++) {
time[i] = (dist[i] + speed[i] - 1) / speed[i]; // ceiling of (dist[i] / speed[i])
}
Array.Sort(time);
for (int i = 0; i < n; i++) {
if (time[i] <= i) {
return i;
}
}
return n;
}
public static void Main(string[] args) {
MonsterElimination me = new MonsterElimination();
int result = me.EliminateMaximum(new int[] {1, 3, 4}, new int[] {1, 1, 1});
Console.WriteLine(result);
}
}The Python code calculates the time taken for each monster to reach the city, sorts these times, and checks at each minute if a monster has reached the city. It's designed to stop when a loss condition is met.
Time Complexity: O(n log n) due to sorting the times.
Space Complexity: O(n) for storing the arrival times.
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.
from bisect import bisect_right
def eliminateMaximum(dist, speed):
n = len(dist)
arrival = sorted((dist[i] + speed[i] - 1) // speed[i] for i in range(n))
return bisect_right(arrival, range(n))
print(eliminateMaximum([1, 3, 4], [1, 1, 1]))function eliminateMaximum(dist, speed) {
let time = dist.map((d, i) => Math.ceil(d / speed[i]));
time.sort((a, b) => a - b);
for (let i = 0; i < time.length; i++) {
if (time[i] <= i) {
return i;
}
}
return time.length;
}
console.log(eliminateMaximum([1, 3, 4], [1, 1, 1]));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.
Time Complexity: O(n log n) due to the sort operation.
Space Complexity: O(n) to store arrival times.
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.
function eliminateMaximum(dist: number[], speed: number[]): number {
const n = dist.length;
const times: number[] = Array(n).fill(0);
for (let i = 0; i < n; ++i) {
times[i] = Math.floor((dist[i] - 1) / speed[i]);
}
times.sort((a, b) => a - b);
for (let i = 0; i < n; ++i) {
if (times[i] < i) {
return i;
}
}
return n;
}func eliminateMaximum(dist []int, speed []int) int {
n := len(dist)
times := make([]int, n)
for i, d := range dist {
times[i] = (d - 1) / speed[i]
}
sort.Ints(times)
for i, t := range times {
if t < i {
return i
}
}
return n
}Complexity comparison
| 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 | – |
Complexity analysis
| 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. |
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.