# Eliminate Maximum Number of Monsters
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/eliminate-maximum-number-of-monsters)
Canonical: https://scaleengineer.com/dsa/problems/eliminate-maximum-number-of-monsters
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Agoda](https://scaleengineer.com/companies/agoda)
---
## 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.length`
* `1 <= n <= 105`
* `1 <= dist[i], speed[i] <= 105`

# Approaches
## Naive Simulation with Linear Scan
This approach simulates the game in a straightforward, minute-by-minute fashion. At each time step `t` (starting from `t=0`), we have one weapon charge available. To maximize the number of monsters we eliminate, it's always best to use our charge on the most immediate threat. This means finding the monster that will reach the city soonest.

The simulation proceeds by repeatedly scanning all remaining monsters to find the one with the minimum arrival time. We then check if we can eliminate it before it reaches the city. If we can, we increment our kill count and continue to the next minute. If not, the game ends, and we return the total number of monsters eliminated up to that point.
**Time:** O(n^2) - The main simulation loop runs up to `n` times. Inside this loop, finding the monster with the minimum arrival time requires a linear scan of the remaining monsters, which takes up to O(n) time. This results in a total time complexity of O(n*n). · **Space:** O(n) - We use a list to store the arrival times of the `n` monsters.
**Pros:** The logic is simple and directly follows the rules of the game.; It's a good starting point for understanding the problem dynamics.
**Cons:** The time complexity of O(n^2) is too slow for the given constraints (n up to 10^5), and will likely result in a 'Time Limit Exceeded' error on most platforms.
### Explanation
The core of this method is a loop that represents the passage of time. We start at `time = 0` and can potentially continue until `time = n-1`.

1.  First, we pre-calculate the arrival time for every monster using floating-point division: `arrivalTime[i] = (double)dist[i] / speed[i]`. We store these in a helper data structure, like a list, which allows for easy removal of monsters.

2.  We then enter the main simulation loop. For each `time` from `0` to `n-1`:
    a. We search through the list of active monsters to find the one with the smallest arrival time. This requires a linear scan of the remaining monsters.
    b. Once we find the most urgent monster, we compare its arrival time to our current `time`. According to the rules, we lose if the monster reaches the city at the exact moment our weapon is charged. Therefore, the condition for a successful elimination is `arrivalTime > time`.
    c. If the condition is met, we eliminate the monster, increment our kill counter, and remove it from our list of active monsters. 
    d. If the condition fails, we cannot eliminate this monster in time. The game ends, and we return the current kill count.

3.  If the simulation loop completes without an early exit, it means we were able to eliminate all `n` monsters.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int eliminateMaximum(int[] dist, int[] speed) {
        int n = dist.length;
        List<Double> arrivalTimes = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            arrivalTimes.add((double) dist[i] / speed[i]);
        }

        int eliminatedCount = 0;
        for (int time = 0; time < n; time++) {
            if (arrivalTimes.isEmpty()) {
                break; // All monsters eliminated
            }

            // Find the monster with the minimum arrival time
            int minIdx = -1;
            double minArrival = Double.POSITIVE_INFINITY;
            for (int i = 0; i < arrivalTimes.size(); i++) {
                if (arrivalTimes.get(i) < minArrival) {
                    minArrival = arrivalTimes.get(i);
                    minIdx = i;
                }
            }

            // Check if we can eliminate it
            if (minArrival <= time) {
                // This monster reaches the city at or before we can shoot
                return eliminatedCount;
            } else {
                // Eliminate the monster
                eliminatedCount++;
                arrivalTimes.remove(minIdx);
            }
        }

        return eliminatedCount;
    }
}
```
### Algorithm
*   Calculate the arrival time for each monster using the formula `arrivalTime = (double)distance / speed`.
*   Store these arrival times in a dynamic list, along with a way to track which monsters are still active.
*   Simulate the game minute by minute, from `time = 0` to `n-1`.
*   In each minute `t`, iterate through all active monsters to find the one with the minimum arrival time.
*   Let the minimum arrival time be `minArrival`.
*   If `minArrival <= t`, the monster reaches the city at or before we can fire our weapon. The game is lost. We break the simulation.
*   If `minArrival > t`, we can successfully eliminate this monster. We increment our count of eliminated monsters and mark this monster as inactive (e.g., by removing it from the list or setting its arrival time to infinity).
*   The final count of eliminated monsters is the result.

## Greedy Approach with Sorting
A more efficient approach comes from a greedy strategy. To maximize the number of monsters we can eliminate, we should always prioritize the monster that will reach the city the soonest. By dealing with the most imminent threat at every step, we maximize our chances of surviving long enough to eliminate more monsters. Any other strategy risks letting a close monster reach the city while we're busy with a farther one.

This greedy strategy can be implemented efficiently by first calculating the arrival time for every monster and then sorting them. Once sorted, we can simulate the game in a single pass.
**Time:** O(n log n) - The dominant operation is sorting the arrival times of the `n` monsters. Calculating the times and the final check both take O(n) time. · **Space:** O(n) - An auxiliary array of size `n` is used to store the arrival times. Some sorting algorithms might use additional space, but it's typically within O(log n) or O(n).
**Pros:** The O(n log n) time complexity is efficient enough for the given constraints.; The logic is clear and directly implements the optimal greedy strategy.
**Cons:** Requires O(n) extra space for the arrival times array.; Uses floating-point arithmetic, which can have precision issues in some problems, though it's safe here.
### Explanation
The implementation of this greedy strategy is straightforward:

1.  **Calculate Arrival Times:** We create an array of size `n` to store the arrival time of each monster. The arrival time for monster `i` is `dist[i] / speed[i]`. To handle fractional results correctly (e.g., a distance of 3 and speed of 2 gives an arrival time of 1.5), we must use floating-point division.

2.  **Sort:** We sort the array of arrival times in ascending order. After sorting, `arrivalTimes[0]` is the time for the monster that will arrive first, `arrivalTimes[1]` is for the second, and so on.

3.  **Simulate and Check:** We then iterate through this sorted array. We can use the loop index `i` to represent the current time. At `time = 0` (for `i=0`), we check the first monster. At `time = 1` (for `i=1`), we check the second, and so on. For the monster at index `i` in the sorted list, we are attempting to eliminate it at time `i`. The game is lost if this monster's arrival time is less than or equal to `i`. If `arrivalTimes[i] <= i`, we return `i` as the total number of monsters eliminated. If we finish the loop, it means we can defeat all `n` monsters, so we return `n`.

```java
import java.util.Arrays;

class Solution {
    public int eliminateMaximum(int[] dist, int[] speed) {
        int n = dist.length;
        double[] arrivalTimes = new double[n];
        for (int i = 0; i < n; i++) {
            arrivalTimes[i] = (double) dist[i] / speed[i];
        }

        Arrays.sort(arrivalTimes);

        for (int i = 0; i < n; i++) {
            // At time i, we are ready to shoot our (i+1)-th monster.
            // We are targeting the i-th monster from the sorted list.
            // If its arrival time is less than or equal to the current time, we lose.
            if (arrivalTimes[i] <= i) {
                return i; // We have successfully eliminated i monsters.
            }
        }

        // If we complete the loop, we can eliminate all monsters.
        return n;
    }
}
```
### Algorithm
*   Create a floating-point array, `arrivalTimes`, of size `n`.
*   For each monster `i`, calculate its arrival time as `arrivalTimes[i] = (double)dist[i] / speed[i]`.
*   Sort the `arrivalTimes` array in non-decreasing order. This arranges the monsters from the most urgent to the least urgent.
*   Initialize a counter for eliminated monsters, `eliminatedCount = 0`.
*   Iterate through the sorted `arrivalTimes` array with an index `i` from `0` to `n-1`. The index `i` also represents the time at which we can make our `(i+1)`-th shot.
*   In each iteration, check if `arrivalTimes[i] <= i`. 
*   If this condition is true, it means the `(i+1)`-th monster (in order of urgency) arrives at or before the time `i` when we are ready to shoot. We lose the game. The number of monsters successfully eliminated is `i`. Return `i`.
*   If the loop completes without this condition ever being met, it means we can eliminate all `n` monsters. Return `n`.

## Greedy Approach with Counting Sort
This approach refines the greedy strategy by optimizing the sorting step. A standard comparison-based sort takes O(n log n) time. However, by observing the constraints on `dist` and `speed`, we can determine that the values we need to sort fall into a predictable and limited integer range. This allows us to use a non-comparison-based sorting algorithm like Counting Sort, which can achieve linear time complexity.

Instead of working with floating-point arrival times, we can work with an integer representation of urgency. For each monster, we calculate the latest possible minute it can be killed before it reaches the city. Then, we count how many monsters fall into each 'latest kill time' bucket and process these buckets in order.
**Time:** O(n + M) - We iterate through the `n` monsters once to populate the counts array (O(n)). Then we iterate through the counts array (size `M`). If `M` is proportional to `n`, the complexity is O(n). · **Space:** O(M) - Where `M` is the range of `max_kill_time` values we track. If we only track up to `n`, this is O(n).
**Pros:** Achieves optimal linear time complexity O(n+M).; Avoids floating-point arithmetic and potential precision errors.
**Cons:** The logic can be slightly less intuitive than the direct sorting approach.; Requires a frequency array whose size depends on the range of input values, which could be large if constraints were different.
### Explanation
The key insight is to avoid floating-point numbers and use integer arithmetic. The condition to survive an encounter with monster `i` at time `t` is `dist[i] > t * speed[i]`. Since all values are integers, this is equivalent to `dist[i] - 1 >= t * speed[i]`, which can be rewritten as `(dist[i] - 1) / speed[i] >= t` using integer division. Let's call `max_kill_time[i] = (dist[i] - 1) / speed[i]`. This is the latest time `t` we can afford to eliminate monster `i`.

Our strategy is still to eliminate monsters with smaller `max_kill_time` first. Instead of sorting an array of these values, we can count their occurrences.

1.  **Counting Frequencies:** We create a frequency array, `counts`, of size `n`. We iterate through each monster, calculate its `max_kill_time`, and if it's less than `n`, we increment `counts[max_kill_time]`. Monsters with `max_kill_time >= n` are no threat within the first `n` minutes, so they don't need to be tracked in this array.

2.  **Simulate with Counts:** We iterate from `time = 0` to `n-1`. We maintain a `backlog` of monsters that are due to be killed. 
    - At each `time`, we add the monsters that just became due: `backlog += counts[time]`.
    - We have one weapon charge at this `time`. If `backlog > 0`, we must use our charge, so we decrement `backlog` and increment our `eliminatedCount`.
    - If after this, `backlog` is still greater than 0, it means there are more monsters due than we could handle. The game is lost. We return the `eliminatedCount`.

3.  If the loop finishes, it means we survived all `n` minutes, so we can eliminate all `n` monsters.

```java
class Solution {
    public int eliminateMaximum(int[] dist, int[] speed) {
        int n = dist.length;
        int[] arrivalTimeCounts = new int[n];

        for (int i = 0; i < n; i++) {
            // Calculate the latest time the monster can be killed
            int timeToArrive = (dist[i] - 1) / speed[i];
            if (timeToArrive < n) {
                arrivalTimeCounts[timeToArrive]++;
            }
        }

        int monsterBacklog = 0;
        for (int time = 0; time < n; time++) {
            // Add monsters that become due at this time
            monsterBacklog += arrivalTimeCounts[time];
            
            if (monsterBacklog > 0) {
                // We must use our shot to eliminate one monster from the backlog
                monsterBacklog--;
            } else {
                // No monsters are currently a threat, we can't lose at this time
                // We can imagine shooting a monster that arrives much later
            }
            
            // After our shot, if there's still a backlog, we lose
            // This check is equivalent to monsterBacklog > time + 1 before shooting
            // A simpler check: if the number of monsters due (monsterBacklog before shooting)
            // is greater than the number of shots we have (time + 1), we lose.
            // Let's rewrite with a clearer check.
        }
        // The above simulation is tricky. A more direct simulation from counts:
        monsterBacklog = 0;
        for (int time = 0; time < n; time++) {
            monsterBacklog += arrivalTimeCounts[time];
            if (monsterBacklog > time + 1) {
                return time + 1;
            }
        }
        // A small correction on the above logic. If at time `t`, backlog > t+1, we have killed t monsters and lose now.
        // Let's use the most robust logic which is equivalent to sorting:
        for (int i = 0; i < n; ++i) {
            dist[i] = (dist[i] - 1) / speed[i];
        }
        Arrays.sort(dist);
        for (int i = 0; i < n; ++i) {
            if (dist[i] < i) {
                return i;
            }
        }
        return n;
    }
}
```
*Note: The provided code snippet uses the integer time calculation but with a standard sort for clarity, as a full counting sort implementation is more verbose. The complexity analysis assumes a true counting sort is used.*
### Algorithm
*   Instead of floating-point arrival times, calculate an integer `max_kill_time` for each monster. This is the latest minute `t` at which we can eliminate it. The formula is `(dist[i] - 1) / speed[i]` using integer division.
*   Create a frequency array, `counts`, of size `n` (or larger, e.g., `100001`, to be safe). `counts[t]` will store the number of monsters with `max_kill_time = t`.
*   Iterate through all monsters, calculate their `max_kill_time`, and update the `counts` array. For any monster with `max_kill_time >= n`, we can simply ignore it or place it in a separate bucket, as it poses no threat to eliminating the first `n` monsters.
*   Initialize `monsters_due = 0`.
*   Iterate with a `time` variable from `0` to `n-1`.
*   In each iteration `time`, add the monsters that become due: `monsters_due += counts[time]`.
*   After adding, `monsters_due` represents the total number of monsters that must be eliminated by or at this `time`.
*   We have one shot at this `time`. If `monsters_due > 0`, we use our shot, so we decrement `monsters_due`.
*   If after using our shot, `monsters_due` is still greater than 0, it means there's at least one monster we couldn't eliminate in time. We lose. The number of monsters killed is `time + 1`.
*   If the loop completes, we can kill all `n` monsters.

# Solutions
### Java

```java
class Solution {
public
  int eliminateMaximum(int[] dist, int[] speed) {
    int n = dist.length;
    int[] times = new int[n];
    for (int i = 0; i < n; ++i) {
      times[i] = (dist[i] - 1) / speed[i];
    }
    Arrays.sort(times);
    for (int i = 0; i < n; ++i) {
      if (times[i] < i) {
        return i;
      }
    }
    return n;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} dist * @param {number[]} speed * @return {number} */ var eliminateMaximum =
  function (dist, speed) {
    let arr = [];
    for (let i = 0; i < dist.length; i++) {
      arr[i] = dist[i] / speed[i];
    }
    arr.sort((a, b) => a - b);
    let ans = 0;
    while (arr[0] > ans) {
      arr.shift();
      ++ans;
    }
    return ans;
  };

```

### CSharp

```csharp
public class Solution {
    public int EliminateMaximum(int[] dist, int[] speed) {
        int n = dist.Length;
        int[] times = new int[n];
        for (int i = 0; i < n; ++i) {
            times[i] = (dist[i] - 1) / speed[i];
        }
        Array.Sort(times);
        for (int i = 0; i < n; ++i) {
            if (times[i] < i) {
                return i;
            }
        }
        return n;
    }
}
```

### CPP

```cpp
class Solution { public: int eliminateMaximum ( vector < int >& dist , vector < int >& speed ) { int n = dist . size (); vector < int > times ; for ( int i = 0 ; i < n ; ++ i ) { times . push_back (( dist [ i ] - 1 ) / speed [ i ]); } sort ( times . begin (), times . end ()); for ( int i = 0 ; i < n ; ++ i ) { if ( times [ i ] < i ) { return i ; } } return n ; } };
```

### Python

```python
class Solution:
    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int: times = sorted((d - 1) // s for d, s in zip(dist, speed)) for i, t in enumerate(times): if t < i: return i return len(times)

```