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.
Example 1:
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.length1 <= n <= 1051 <= dist[i], speed[i] <= 105This approach involves computing the exact time each monster will take to reach the city and then eliminating them in the order of their arrival times. The goal is to eliminate as many monsters as possible before any monster reaches the city.
The C solution calculates the time each monster takes to reach the city and sorts these times. It then iterates over the sorted times, using each minute to eliminate the monster that reaches the city next. If at any point the current minute is equal to or greater than the time a monster reaches the city, the process stops.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n) due to sorting the times.
Space Complexity: O(n) to store the arrival times.
This approach improves the efficiency of eliminating the maximum number of monsters by using a binary search method. It pre-calculates when a monster will reach the city and uses efficient search techniques to make decisions dynamically during the elimination process.
By using a library function like bisect_right in Python, the code finds the largest index to insert a value (in this case to simulate minutes passing) while maintaining order. This efficiently tells us the maximum monsters that can be eliminated as time progresses.
JavaScript
Time Complexity: O(n log n) due to the sort operation.
Space Complexity: O(n) to store arrival times.
| Approach | Complexity |
|---|---|
| Calculate Arrival Times and Eliminate in Order | Time Complexity: O(n log n) due to sorting the times. |
| Binary Search Optimization with Sorted Distances | Time Complexity: O(n log n) due to the sort operation. |
Eliminate Maximum Number of Monsters - Leetcode 1921 - Weekly Contest 248 - Python • NeetCode • 8,680 views views
Watch 9 more video solutions →Practice Eliminate Maximum Number of Monsters with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor