1921. Eliminate Maximum Number of Monsters - Explanation

Description

Monster i starts dist[i] kilometers away and moves toward the city at speed[i] kilometers per minute. You can eliminate one monster at time 0, then one at each whole minute. If any surviving monster reaches the city, you lose immediately, including when its arrival coincides with a shot time. Return the greatest number of monsters you can eliminate before losing, or the total number if you can eliminate them all.

Example 1:

Input: dist = [2,4,6]
speed = [1,1,1]

Output: 3

Explanation: Eliminate the monsters at minutes 0, 1, and 2. Their arrival times are 2, 4, and 6, so all three shots occur in time.

Example 2:

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

Output: 1

Explanation: Both monsters reach the city at minute 1. Only one can be eliminated at minute 0; the other arrives before the next shot.

Example 3:

Input: dist = [3,5]
speed = [2,2]

Output: 2

Explanation: The arrival times are 1.5 and 2.5 minutes. Eliminate the first monster at minute 0 and the second at minute 1, before either arrival.

Constraints:

1 <= dist.length <= 100000
dist.length == speed.length
1 <= dist[i], speed[i] <= 100000

Topics

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Sorting - The main solution sorts arrival times to process monsters in order of urgency
Greedy Algorithms - Understanding that eliminating the earliest-arriving monster first is always optimal
Min-Heap / Priority Queue - An alternative approach uses a min-heap to extract minimum arrival times on demand

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

Compute minReach[i] = ceil(dist[i] / speed[i]) for each monster.
Sort minReach in ascending order.
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.
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

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

        for (int i = 0; i < n; i++) {
            minReach[i] = (int) Math.ceil((double) dist[i] / speed[i]);
        }

        Arrays.sort(minReach);

        int res = 0;
        for (int minute = 0; minute < n; minute++) {
            if (minute >= minReach[minute]) {
                return res;
            }
            res++;
        }

        return res;
    }
}

class Solution {
public:
    int eliminateMaximum(vector<int>& dist, vector<int>& speed) {
        int n = dist.size();
        vector<int> minReach(n);

        for (int i = 0; i < n; i++) {
            minReach[i] = ceil((double)dist[i] / speed[i]);
        }

        sort(minReach.begin(), minReach.end());

        int res = 0;
        for (int minute = 0; minute < n; minute++) {
            if (minute >= minReach[minute]) {
                return res;
            }
            res++;
        }

        return res;
    }
};

class Solution {
    /**
     * @param {number[]} dist
     * @param {number[]} speed
     * @return {number}
     */
    eliminateMaximum(dist, speed) {
        let n = dist.length;
        let minReach = new Array(n);

        for (let i = 0; i < n; i++) {
            minReach[i] = Math.ceil(dist[i] / speed[i]);
        }

        minReach.sort((a, b) => a - b);

        let res = 0;
        for (let minute = 0; minute < n; minute++) {
            if (minute >= minReach[minute]) {
                return res;
            }
            res++;
        }

        return res;
    }
}

public class Solution {
    public int EliminateMaximum(int[] dist, int[] speed) {
        int n = dist.Length;
        int[] minReach = new int[n];

        for (int i = 0; i < n; i++) {
            minReach[i] = (int)Math.Ceiling((double)dist[i] / speed[i]);
        }

        Array.Sort(minReach);

        int res = 0;
        for (int minute = 0; minute < n; minute++) {
            if (minute >= minReach[minute]) {
                return res;
            }
            res++;
        }

        return res;
    }
}

class Solution {
    fun eliminateMaximum(dist: IntArray, speed: IntArray): Int {
        val n = dist.size
        val minReach = IntArray(n) { i ->
            (dist[i] + speed[i] - 1) / speed[i]
        }

        minReach.sort()

        var res = 0
        for (minute in 0 until n) {
            if (minute >= minReach[minute]) {
                return res
            }
            res++
        }

        return res
    }
}

class Solution {
    func eliminateMaximum(_ dist: [Int], _ speed: [Int]) -> Int {
        let n = dist.count
        var minReach = [Int](repeating: 0, count: n)

        for i in 0..<n {
            minReach[i] = (dist[i] + speed[i] - 1) / speed[i]
        }

        minReach.sort()

        var res = 0
        for minute in 0..<n {
            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

Overwrite dist[i] with ceil(dist[i] / speed[i]).
Sort dist in ascending order.
For each minute from 0 to n - 1:
- If minute >= dist[minute], return minute.
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)

public class Solution {
    public int eliminateMaximum(int[] dist, int[] speed) {
        int n = dist.length;
        for (int i = 0; i < n; i++) {
            dist[i] = (int) Math.ceil((double) dist[i] / speed[i]);
        }

        Arrays.sort(dist);
        for (int minute = 0; minute < n; minute++) {
            if (minute >= dist[minute]) {
                return minute;
            }
        }

        return n;
    }
}

class Solution {
public:
    int eliminateMaximum(vector<int>& dist, vector<int>& speed) {
        int n = dist.size();
        for (int i = 0; i < n; i++) {
            dist[i] = ceil((double)dist[i] / speed[i]);
        }

        sort(dist.begin(), dist.end());
        for (int minute = 0; minute < n; minute++) {
            if (minute >= dist[minute]) {
                return minute;
            }
        }

        return n;
    }
};

class Solution {
    /**
     * @param {number[]} dist
     * @param {number[]} speed
     * @return {number}
     */
    eliminateMaximum(dist, speed) {
        let n = dist.length;
        for (let i = 0; i < n; i++) {
            dist[i] = Math.ceil(dist[i] / speed[i]);
        }

        dist.sort((a, b) => a - b);
        for (let minute = 0; minute < n; minute++) {
            if (minute >= dist[minute]) {
                return minute;
            }
        }

        return n;
    }
}

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

Push dist[i] / speed[i] into a min-heap for each monster.
Initialize res = 0 to count eliminations.
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.
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

public class Solution {
    public int eliminateMaximum(int[] dist, int[] speed) {
        PriorityQueue<Double> minHeap = new PriorityQueue<>();
        for (int i = 0; i < dist.length; i++) {
            minHeap.add((double) dist[i] / speed[i]);
        }

        int res = 0;
        while (!minHeap.isEmpty()) {
            if (res >= minHeap.poll()) {
                return res;
            }
            res++;
        }

        return res;
    }
}

class Solution {
public:
    int eliminateMaximum(vector<int>& dist, vector<int>& speed) {
        priority_queue<double, vector<double>, greater<double>> minHeap;
        for (int i = 0; i < dist.size(); i++) {
            minHeap.push((double)dist[i] / speed[i]);
        }

        int res = 0;
        while (!minHeap.empty()) {
            if (res >= minHeap.top()) {
                return res;
            }
            minHeap.pop();
            res++;
        }

        return res;
    }
};

class Solution {
    /**
     * @param {number[]} dist
     * @param {number[]} speed
     * @return {number}
     */
    eliminateMaximum(dist, speed) {
        const minHeap = new MinPriorityQueue();
        for (let i = 0; i < dist.length; i++) {
            minHeap.enqueue(dist[i] / speed[i]);
        }

        let res = 0;
        while (!minHeap.isEmpty()) {
            if (res >= minHeap.dequeue().element) {
                return res;
            }
            res++;
        }

        return res;
    }
}

impl Solution {
    pub fn eliminate_maximum(dist: Vec<i32>, speed: Vec<i32>) -> i32 {
        let mut min_heap = BinaryHeap::new();
        for i in 0..dist.len() {
            // Use Reverse for min-heap behavior; store as (numerator, denominator)
            // arrival time = dist[i] / speed[i] as float, but we can compare fractions
            // For simplicity, use ceiling integer division
            let arrival = (dist[i] + speed[i] - 1) / speed[i];
            min_heap.push(std::cmp::Reverse(arrival));
        }

        let mut res = 0;
        while let Some(std::cmp::Reverse(arrival)) = min_heap.pop() {
            if res >= arrival {
                return res;
            }
            res += 1;
        }

        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.