{x}
blog image

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 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

Problem Description

The problem involves defending a city from n monsters approaching at different speeds and distances. You have a weapon that eliminates one monster per minute, starting fully charged. The goal is to determine the maximum number of monsters you can eliminate before any reach the city. A monster reaching the city at the exact moment the weapon charges is considered a loss.

Solution Approach: Greedy with Sorting

The solution employs a greedy strategy combined with sorting for efficiency. The core idea is to prioritize eliminating monsters that pose the most immediate threat. This is achieved by calculating the time each monster takes to reach the city and then sorting these times.

  1. Calculate Time to Reach: For each monster i, calculate the time t_i it takes to reach the city: t_i = floor(dist[i] - 1) / speed[i]). We subtract 1 from dist[i] because if a monster arrives exactly when the weapon is ready, it's still a loss. floor() ensures we take the integer part since the weapon only charges in discrete one-minute intervals.

  2. Sort Times: Sort the calculated times t_i in ascending order. This prioritizes monsters arriving sooner.

  3. Greedy Elimination: Iterate through the sorted times. If the time t_i is less than the current minute i (index in the sorted array), it means the monster arrives before the weapon is ready, and we've lost. The function returns i (the number of monsters eliminated before the loss).

  4. All Monsters Eliminated: If the loop completes without a loss, it means all monsters were successfully eliminated, and the function returns n.

Time and Space Complexity Analysis

  • Time Complexity: O(n log n), dominated by the sorting step (using a comparison-based sort like merge sort or quicksort). The other operations (calculation of times and iteration) are O(n).

  • Space Complexity: O(n) to store the times array. The space used by the sorting algorithm depends on the implementation but is generally O(log n) or O(n) in the worst case for some algorithms.

Code Implementation in Multiple Languages

The following provides code implementations demonstrating the solution in several programming languages:

Python:

import math
 
def eliminateMaximum(dist, speed):
    times = sorted([(math.floor((d - 1) / s)) for d, s in zip(dist, speed)])
    for i, t in enumerate(times):
        if t < i:
            return i
    return len(times)

Java:

import java.util.Arrays;
 
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] = (int) Math.floor((double)(dist[i] - 1) / speed[i]);
        }
        Arrays.sort(times);
        for (int i = 0; i < n; i++) {
            if (times[i] < i) {
                return i;
            }
        }
        return n;
    }
}

C++:

#include <vector>
#include <algorithm>
#include <cmath>
 
class Solution {
public:
    int eliminateMaximum(std::vector<int>& dist, std::vector<int>& speed) {
        std::vector<int> times;
        for (size_t i = 0; i < dist.size(); ++i) {
            times.push_back(static_cast<int>(std::floor((double)(dist[i] - 1) / speed[i])));
        }
        std::sort(times.begin(), times.end());
        for (size_t i = 0; i < times.size(); ++i) {
            if (times[i] < i) {
                return i;
            }
        }
        return times.size();
    }
};

JavaScript:

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

These code examples all follow the same algorithmic approach, demonstrating the solution's adaptability across different programming languages. Remember to handle potential integer division issues appropriately in your chosen language (as shown in the examples above).