1921. Eliminate Maximum Number of Monsters - Explanation

Problem Link

1. Sorting

Intuition

The weapon needs 1 minute to recharge after each shot. To maximize eliminations, we should prioritize monsters that will reach the city soonest. For each monster, we calculate the time it takes to arrive (distance / speed, rounded up). Sorting these arrival times lets us greedily eliminate monsters in order of urgency. If at any minute the earliest uneliminated monster has already arrived, the game ends.

Algorithm

1. Compute minReach[i] = ceil(dist[i] / speed[i]) for each monster.
2. Sort minReach in ascending order.
3. Iterate through the sorted array with index minute:
   • If minute >= minReach[minute], the monster arrives before we can shoot it. Return the current count.
   • Otherwise, increment the elimination count.
4. Return the total count if all monsters are eliminated.

class Solution:
    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:
        minReach = [math.ceil(d / s) for d, s in zip(dist, speed)]
        minReach.sort()

        res = 0
        for minute in range(len(minReach)):
            if minute >= minReach[minute]:
                return res
            res += 1

        return res

Time & Space Complexity

• Time complexity: $O(n \log n)$
• Space complexity: $O(n)$

---

2. Sorting (Overwriting Input Array)

Intuition

This is the same approach as above, but we save space by reusing the input dist array to store arrival times instead of creating a new array. The logic remains identical: compute arrival times, sort, and check if we can eliminate each monster before it arrives.

Algorithm

1. Overwrite dist[i] with ceil(dist[i] / speed[i]).
2. Sort dist in ascending order.
3. For each minute from 0 to n - 1:
   • If minute >= dist[minute], return minute.
4. Return n if all monsters are eliminated.

class Solution:
    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:
        for i in range(len(dist)):
            dist[i] = math.ceil(dist[i] / speed[i])

        dist.sort()
        for minute in range(len(dist)):
            if minute >= dist[minute]:
                return minute

        return len(dist)

Time & Space Complexity

• Time complexity: $O(n \log n)$
• Space complexity: $O(1)$ or $O(n)$ depending on the sorting algorithm.

---

3. Min-Heap

Intuition

Instead of sorting all arrival times upfront, we can use a min-heap to extract the minimum arrival time on demand. This still achieves the same goal of processing monsters in order of how soon they reach the city. We pop from the heap one at a time and check if the monster arrives before the current minute.

Algorithm

1. Push dist[i] / speed[i] into a min-heap for each monster.
2. Initialize res = 0 to count eliminations.
3. While the heap is non-empty:
   • Pop the smallest arrival time.
   • If res >= arrival_time, the monster has reached the city. Return res.
   • Otherwise, increment res.
4. Return res after all monsters are eliminated.

class Solution:
    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:
        minHeap = []
        for i in range(len(dist)):
            heapq.heappush(minHeap, dist[i] / speed[i])

        res = 0
        while minHeap:
            if res >= heapq.heappop(minHeap):
                return res
            res += 1

        return res

Time & Space Complexity

• Time complexity: $O(n \log n)$
• Space complexity: $O(n)$

---

Common Pitfalls

Using Floor Division Instead of Ceiling

When calculating arrival time, you need ceil(dist[i] / speed[i]) because a monster at distance 3 with speed 2 arrives at minute 2 (not 1.5). Using floor division or integer division without rounding up causes incorrect arrival time calculations, leading to wrong elimination counts.

Forgetting to Sort the Arrival Times

The greedy approach only works when monsters are processed in order of their arrival times. Without sorting, you might try to eliminate a monster that arrives later while an earlier one reaches the city, giving incorrect results.

Off-by-One Error in the Comparison

The condition should be minute >= minReach[minute] (monster arrives at or before the current minute), not minute > minReach[minute]. If a monster arrives exactly at minute 2 and we're at minute 2, we cannot eliminate it in time since we shoot at the start of each minute.