3.35 Eliminate Maximum Number of Monsters

3.35.1 Problem Metadata

3.35.2 Description

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.

3.35.3 Examples

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

Example 4:

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

3.35.4 Constraints

  • n == dist.length == speed.length
  • 1 <= n <= 10^5
  • 1 <= dist[i], speed[i] <= 10^5

3.35.5 Solution 1

3.35.5.1 Walkthrough

The key insight is that we should eliminate monsters in order of their arrival time, not their current distance. This greedy approach ensures we always eliminate the most urgent threat first.

Step-by-step approach:

  1. Calculate arrival time: For each monster at distance dist[i] moving at speed[i], it will reach the city at time ?dist[i] / speed[i]? minutes. We use ceiling because if a monster arrives at time 1.5, it effectively arrives at minute 2.

  2. Sort by arrival time: Sort monsters by when they’ll arrive. This tells us the optimal elimination order - always eliminate the monster that will arrive soonest.

  3. Simulate elimination: Starting at time 0 with a charged weapon:

    • At each minute t, check if the monster scheduled to arrive at arrival[t] has already reached or will reach the city before we can eliminate it
    • If arrival[t] <= t, the monster has arrived and we lose
    • Otherwise, eliminate the monster and move to the next minute

  4. Key observation: Since we eliminate one monster per minute starting at minute 0, the time elapsed t is always equal to the count of monsters eliminated. This means:

    • At minute 0: we’ve eliminated 0 monsters (about to eliminate the 1st)
    • At minute 1: we’ve eliminated 1 monster (about to eliminate the 2nd)
    • At minute t: we’ve eliminated t monsters (about to eliminate the (t+1)th)

    This allows us to use a single loop variable t instead of tracking both timeElapsed and count separately!

3.35.5.2 Analysis

  • Time Complexity: O(n log n) - Dominated by sorting the arrival times array
  • Space Complexity: O(n) - For storing the arrival times array

3.35.5.3 Implementation Steps

  1. Calculate arrival time for each monster: ?dist[i] / speed[i]?
  2. Sort monsters by arrival time (ascending order)
  3. Iterate through sorted arrival times:
    • At minute t, check if arrival[t] <= t (monster has arrived)
    • If yes, return t (number of monsters eliminated)
    • If no, continue to next minute
  4. If all monsters eliminated, return n

3.35.5.4 Code - Java

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

        // Calculate arrival time for each monster
        int[] arrival = new int[n];
        for (int i = 0; i < n; i++) {
            arrival[i] = (int) Math.ceil((double) dist[i] / speed[i]);
        }

        // Sort by arrival time - eliminate monsters in order of urgency
        Arrays.sort(arrival);

        // Simulate elimination: at minute t, check if monster t has arrived
        for (int t = 0; t < n; t++) {
            if (arrival[t] <= t) {
                // Monster has arrived before we could eliminate it
                return t;
            }
        }

        // All monsters eliminated
        return n;
    }
}

3.35.6 Notes

  • Pattern: Greedy + Sorting
  • Key Insight: The optimal strategy is to always eliminate the monster with the earliest arrival time, regardless of their current distance or speed. Sorting by arrival time naturally gives us this order.
  • Why Greedy Works: Since we can only eliminate one monster per minute, we must prioritize by urgency (arrival time). Any other ordering would allow an earlier-arriving monster to reach the city.
  • Edge Case: When arrival[t] == t, the monster reaches the city at the exact moment the weapon charges, which counts as a loss per the problem statement.
  • Optimization: The time elapsed t is implicitly equal to the count of monsters eliminated, so we don’t need a separate counter variable.
  • Common Mistakes:
    • Sorting by distance instead of arrival time - this fails when a far-away fast monster arrives before a close slow monster
    • Forgetting to use ceiling division - fractional arrival times must be rounded up
    • Off-by-one errors with the condition arrival[t] <= t vs arrival[t] < t