1921. Eliminate Maximum Number of Monsters LeetCode Solution
In this guide, you will get 1921. Eliminate Maximum Number of Monsters LeetCode Solution with the best time and space complexity. The solution to Eliminate Maximum Number of Monsters problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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.
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
Complexity Analysis
Time Complexity: O(\texttt{sort})
Space Complexity: O(n)
1921. Eliminate Maximum Number of Monsters LeetCode Solution in C++
class Solution {
public:
int eliminateMaximum(vector<int>& dist, vector<int>& speed) {
const int n = dist.size();
vector<int> arrivalTime(n);
for (int i = 0; i < n; ++i)
arrivalTime[i] = (dist[i] - 1) / speed[i];
ranges::sort(arrivalTime);
for (int i = 0; i < n; ++i)
if (i > arrivalTime[i])
return i;
return n;
}
}; /* code provided by PROGIEZ */
1921. Eliminate Maximum Number of Monsters LeetCode Solution in Java
class Solution {
public int eliminateMaximum(int[] dist, int[] speed) {
final int n = dist.length;
int[] arrivalTime = new int[n];
for (int i = 0; i < n; ++i)
arrivalTime[i] = (dist[i] - 1) / speed[i];
Arrays.sort(arrivalTime);
for (int i = 0; i < n; ++i)
if (i > arrivalTime[i])
return i;
return n;
}
} // code provided by PROGIEZ
1921. Eliminate Maximum Number of Monsters LeetCode Solution in Python
class Solution:
def eliminateMaximum(self, dist: list[int], speed: list[int]) -> int:
for i, arrivalTime in enumerate(
sorted([(d - 1) // s for d, s in zip(dist, speed)])):
if i > arrivalTime:
return i
return len(dist) # code by PROGIEZ
