Code Implementation

class Solution:
    def eliminateMaximum(self, dist, speed):
        # Calculate the time each monster reaches the city
        times = [(d - 1) // s + 1 for d, s in zip(dist, speed)]
        times.sort()
        for minute, t in enumerate(times):
            if t <= minute:
                return minute
        return len(dist)
      

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

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] + 1;
        }
        Arrays.sort(times);
        for (int minute = 0; minute < n; ++minute) {
            if (times[minute] <= minute) return minute;
        }
        return n;
    }
}
      

var eliminateMaximum = function(dist, speed) {
    let times = dist.map((d, i) => Math.floor((d - 1) / speed[i]) + 1);
    times.sort((a, b) => a - b);
    for (let minute = 0; minute < times.length; ++minute) {
        if (times[minute] <= minute) return minute;
    }
    return times.length;
};
      

Problem Description

You are given two integer arrays, dist and speed, both of length n. Each element dist[i] represents the initial distance of the i-th monster from the city, and speed[i] represents the speed at which the i-th monster is approaching.

Every minute, you can eliminate exactly one monster before any of them move. At the end of each minute, all remaining monsters move towards the city according to their speed. If any monster reaches the city (distance ≤ 0), the game ends immediately.

Your task is to determine the maximum number of monsters you can eliminate before any monster reaches the city.

• There is only one valid solution for each input.
• You cannot eliminate more than one monster per minute.
• Once a monster is eliminated, it cannot be chosen again.

Thought Process

Let's break down the problem. We need to eliminate as many monsters as possible before any of them reaches the city. Each minute, we can only eliminate one monster, and after that, all remaining monsters move closer.

A brute-force approach would be to simulate each minute, checking all monsters' positions and deciding which one to eliminate. But this quickly becomes inefficient, especially with larger inputs.

To optimize, we need to focus on the most urgent threats: the monsters that will reach the city first. If we always eliminate the monster that is closest to arriving, we delay the loss for as long as possible. Thus, we should sort monsters by their "arrival time" (how many minutes until each reaches the city) and eliminate in that order.

The key insight is: the monster with the earliest arrival time is always the biggest threat. If we can't eliminate that monster before it arrives, the game ends.

Solution Approach

• Step 1: Calculate Arrival Times
  For each monster, compute how many minutes it will take to reach the city. This is ceil(dist[i] / speed[i]). Since we eliminate before monsters move, we can use integer math: (dist[i] - 1) // speed[i] + 1.
• Step 2: Sort Arrival Times
  Sort the monsters by their arrival times in ascending order. This helps us prioritize which monster to eliminate first.
• Step 3: Simulate Elimination
  For each minute, eliminate the monster with the next earliest arrival time. If at any minute, the next monster's arrival time is less than or equal to the current minute, it means that monster has already reached the city, and the game ends.
• Step 4: Return the Result
  If we successfully eliminate all monsters before any reaches the city, return the total number of monsters. Otherwise, return the number eliminated before the first monster arrived.

This algorithm is efficient because sorting the arrival times allows us to process monsters in the order of urgency, ensuring we always make the optimal elimination choice.

Example Walkthrough

Let's use dist = [1,3,4] and speed = [1,1,1] as an example.

• Step 1: Calculate Arrival Times
  
  • Monster 0: (1-1)//1 + 1 = 1
  • Monster 1: (3-1)//1 + 1 = 3
  • Monster 2: (4-1)//1 + 1 = 4
  Arrival times: [1, 3, 4]
• Step 2: Sort Arrival Times
  Sorted: [1, 3, 4]
• Step 3: Simulate Elimination
  
  • Minute 0: Eliminate monster with arrival time 1 (Monster 0). Remaining: [3, 4]
  • Minute 1: Eliminate monster with arrival time 3 (Monster 1). Remaining: [4]
  • Minute 2: Eliminate monster with arrival time 4 (Monster 2). Remaining: []
  At each minute, the next monster's arrival time is greater than the minute, so we can eliminate all monsters.
• Step 4: Result
  All 3 monsters eliminated before any reaches the city. Return 3.

If instead, the input was dist = [1,1,2,3], speed = [1,1,1,1], arrival times would be [1,1,2,3]. At minute 0, eliminate one monster with arrival 1; at minute 1, the next monster with arrival 1 has already reached the city, so the answer is 1.

Time and Space Complexity

• Brute-force Approach:
  • Time: O(n²) — Simulating each minute and updating all monsters' positions.
  • Space: O(n) — Storing positions of monsters.
• Optimized Approach (Arrival Time Sort):
  • Time: O(n log n) — Calculating arrival times (O(n)) and sorting them (O(n log n)).
  • Space: O(n) — Storing the arrival times array.

The optimized approach is much more efficient, especially for large numbers of monsters.

Summary

In summary, the problem is best solved by focusing on each monster's arrival time, sorting these times, and always eliminating the monster that is closest to arriving. This greedy strategy ensures that you always maximize the number of monsters eliminated before the city is breached. The approach is both simple and efficient, relying on sorting and a single pass through the sorted list, making it well-suited for large input sizes.