#1921

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Eliminate Maximum Number of Monsters

Eliminate monsters by strategically using a weapon in a video game to stop them before they reach your city.

Problem Statement

You are defending a city from a group of n monsters. Each monster is initially at a certain distance from the city, given by the array dist, where dist[i] is the initial distance in kilometers of the ith monster from the city. Each monster walks toward the city at a constant speed, which is represented by the array speed, where speed[i] is the speed of the ith monster in kilometers per minute.

You have a weapon that charges for one minute and can eliminate a monster once fully charged. The weapon is ready at the start. Your goal is to find the maximum number of monsters you can eliminate before any monster reaches the city, considering their initial distance and constant speed.

Examples

Example 1

Input: dist = [1,3,4], speed = [1,1,1]

Output: 3

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

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

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

Solution Approach

Greedy Choice Based on Time

To solve this, calculate the time each monster takes to reach the city. For each monster, the time is given by dist[i] / speed[i]. Sort the monsters by their time to arrive, then eliminate them in order of their arrival time. This ensures that you eliminate the monsters who are the closest to the city first, maximizing the number of eliminations before the city is reached.

Handling the Weapon Charge

As the weapon charges one minute at a time, you need to ensure that you only eliminate monsters that haven't yet reached the city by the time the weapon is ready. Each minute, check if the next monster's time to arrive is greater than or equal to the time elapsed. If it is, eliminate the monster and proceed; otherwise, stop.

Sorting and Time Complexity

Sorting the monsters by their time to reach the city ensures that you efficiently choose which monster to eliminate first. The time complexity is O(n log n) due to the sorting step, which is the most expensive operation in the solution. This is followed by a single pass through the array to count eliminations.

Complexity Analysis

Metric	Value
Time	O(n \cdot \log{}n)
Space	O(n)

The solution involves sorting the monsters by their time to reach the city, which takes O(n log n) time. After sorting, we simply iterate through the array once, making the overall time complexity O(n log n). The space complexity is O(n) to store the distances, speeds, and times for each monster.

What Interviewers Usually Probe

Candidate identifies the greedy strategy and time-based elimination process.
Candidate correctly explains sorting and how the time to reach the city affects the elimination order.
Candidate optimizes the solution with time complexity analysis and justifies the O(n log n) time complexity.

Common Pitfalls or Variants

Common pitfalls

Not considering the time it takes for each monster to reach the city and eliminating in the wrong order.
Misunderstanding that the weapon takes time to charge, affecting the timing of eliminations.
Failing to correctly handle edge cases where the monsters are too close to the city when the weapon is ready.

Follow-up variants

What if the weapon charges faster or has a different charging time?
What if monsters move at different speeds but have the same distance?
What if there is a limit on how many monsters can be eliminated?

FAQ

What is the greedy strategy in the "Eliminate Maximum Number of Monsters" problem?

The greedy strategy in this problem involves eliminating the monsters in the order of their arrival time, ensuring the closest monsters are dealt with first.

How do you calculate the time for a monster to reach the city?

You calculate the time for each monster by dividing its initial distance by its speed, i.e., dist[i] / speed[i].

What are the main challenges of this problem?

The main challenge is efficiently managing the weapon charge time while sorting the monsters based on their arrival times and ensuring no monster reaches the city before being eliminated.

What is the time complexity of this problem?

The time complexity is O(n log n) due to the sorting step. The rest of the solution involves a single pass through the list, which is O(n).

How does GhostInterview help with "Eliminate Maximum Number of Monsters"?

GhostInterview provides insights into greedy algorithms, time management, and common pitfalls, ensuring you avoid mistakes in the elimination process.

terminal

Solution

Solution 1: Sorting + Greedy

We use the $\textit{times}$ array to record the latest time each monster can be eliminated. For the $i$-th monster, the latest time it can be eliminated is:

1

2

3

4

5

6

7

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)

Continue Practicing

#1877 minimize maximum pair sum in array #1968 array with elements not equal to average of neighbors #1846 maximum element after decreasing and rearranging