Eliminate Maximum Number of Monsters Leetcode Solution

Page Contents

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 meters of the ith monster from the city.

See Also: Weekly Contest 248

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 meters per minute.

The monsters start moving at minute 0. You have a weapon that you can choose to use at the start of every minute, including minute 0. You cannot use the weapon in the middle of a minute. The weapon can eliminate any monster that is still alive. You lose when any monster reaches your city. If a monster reaches the city exactly at the start of a minute, it counts as a loss, and the game ends before you can use your weapon in that minute.

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:
At the start of minute 0, the distances of the monsters are [1,3,4], you eliminate the first monster.
At the start of minute 1, the distances of the monsters are [X,2,3], you don't do anything.
At the start of minute 2, the distances of the monsters are [X,1,2], you eliminate the second monster.
At the start of minute 3, the distances of the monsters are [X,X,1], 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:
At the start of minute 0, the distances of the monsters are [1,1,2,3], you eliminate the first monster.
At the start of minute 1, 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:
At the start of minute 0, the distances of the monsters are [3,2,4], you eliminate the first monster.
At the start of minute 1, 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

Program C++

class Solution {
public:
    int eliminateMaximum(vector<int>& dist, vector<int>& speed) {
        int n=dist.size();
        vector<int> temp(n);
		
        // calculate time req for each monster to reach city
        for(int i=0;i<n;i++){
            temp[i] = ceil ( (1.0*dist[i])/speed[i]);
        }
		
		// Sort according to their time
        sort(temp.begin(),temp.end());  // We are sorting because we want to kill those monsters first which take less time to reach the city
        int time=1;
		
		// Checking how many monsters we can kill
        for(int i=0;i<n;i++){
            if(time>temp[i]){  // This means current monster reached the city before we can kill it
                return i;
            }
            time++;
        }
        return n;  
    }
};

Program Python

class Solution:
    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:
        res, t = 0, []
        for s, v in zip(dist, speed):
            t.append(s/v)
        t.sort()
        for i in range(len(dist)):
            if t[i] > i:
                res += 1
            else:
                break
        return res

Program Java

class Solution {
    public int eliminateMaximum(int[] dist, int[] speed) {
        /* Calculate the time for each monster to reach the
           city and start elimiating one every minute starting
           from 0 with one with least time until any monster
           reaches a city. */
        PriorityQueue<Double> pq = new PriorityQueue<>();
        for (int i = 0; i < dist.length; i++) {
            pq.add(dist[i] * 1.0 / speed[i]);
        }
        
        double min = 0.0;
        int count = 0;
        while (!pq.isEmpty() && pq.poll() > min) {
            min += 1.0;
            count++;
        }
        
        return count;
    }
}

Leave a Comment

error: Content is protected !!
Please Click on 1 or 2 Ads to help us run this site.