# Eliminate Maximum Number of Monsters Leetcode Solution

Page Contents

## Eliminate Maximum Number of Monsters

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 meters 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 meters per minute.

The monsters start moving at minute 0. You have a weapon that you can choose to use at the start of every minute, including minute 0. You cannot use the weapon in the middle of a minute. The weapon can eliminate any monster that is still alive. You lose when any monster reaches your city. If a monster reaches the city exactly at the start of a minute, it counts as a loss, and the game ends before you can use your weapon in that minute.

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:
At the start of minute 0, the distances of the monsters are [1,3,4], you eliminate the first monster.
At the start of minute 1, the distances of the monsters are [X,2,3], you don't do anything.
At the start of minute 2, the distances of the monsters are [X,1,2], you eliminate the second monster.
At the start of minute 3, the distances of the monsters are [X,X,1], 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:
At the start of minute 0, the distances of the monsters are [1,1,2,3], you eliminate the first monster.
At the start of minute 1, 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:
At the start of minute 0, the distances of the monsters are [3,2,4], you eliminate the first monster.
At the start of minute 1, 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`

## Solution

Program C++

``````class Solution {
public:
int eliminateMaximum(vector<int>& dist, vector<int>& speed) {
int n=dist.size();
vector<int> temp(n);

// calculate time req for each monster to reach city
for(int i=0;i<n;i++){
temp[i] = ceil ( (1.0*dist[i])/speed[i]);
}

// Sort according to their time
sort(temp.begin(),temp.end());  // We are sorting because we want to kill those monsters first which take less time to reach the city
int time=1;

// Checking how many monsters we can kill
for(int i=0;i<n;i++){
if(time>temp[i]){  // This means current monster reached the city before we can kill it
return i;
}
time++;
}
return n;
}
};``````

Program Python

``````class Solution:
def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:
res, t = 0, []
for s, v in zip(dist, speed):
t.append(s/v)
t.sort()
for i in range(len(dist)):
if t[i] > i:
res += 1
else:
break
return res``````

Program Java

``````class Solution {
public int eliminateMaximum(int[] dist, int[] speed) {
/* Calculate the time for each monster to reach the
city and start elimiating one every minute starting
from 0 with one with least time until any monster
reaches a city. */
PriorityQueue<Double> pq = new PriorityQueue<>();
for (int i = 0; i < dist.length; i++) {