Leetcode 1921: Eliminate Maximum Number of Monsters
You are defending your city from a group of n monsters. You are given two arrays dist and speed, where dist[i] is the initial distance of the ith monster from the city, and speed[i] is the speed of the ith monster in kilometers per minute. Your weapon takes one minute to charge and can eliminate one monster once fully charged. The game ends if any monster reaches the city before your weapon is ready. Return the maximum number of monsters you can eliminate or n if all monsters can be eliminated before they reach the city.
Problem
Approach
Steps
Complexity
Input: You are given two arrays dist and speed, both of size n. dist[i] is the initial distance of the ith monster, and speed[i] is the speed of the ith monster.
Example: dist = [2,4,6], speed = [2,1,1]
Constraints:
• 1 <= n <= 10^5
• 1 <= dist[i], speed[i] <= 10^5
Output: Return the maximum number of monsters that can be eliminated before any of them reach the city, or return n if all monsters can be eliminated.
Example: 3
Constraints:
Goal: Calculate the time each monster takes to reach the city, sort them, and eliminate monsters one by one until any of them reach the city.
Steps:
• For each monster, calculate the time it takes to reach the city: dist[i] / speed[i].
• Sort the times in ascending order.
• Iterate through the sorted times, and eliminate monsters as long as their arrival time is greater than the time elapsed (which increases with each elimination).
Goal: Ensure that the input follows the constraint limits for time and space efficiency.
Steps:
• n can go up to 10^5, so the solution needs to handle large inputs efficiently.
• Each dist[i] and speed[i] is guaranteed to be between 1 and 10^5.
Assumptions:
• The input arrays dist and speed will always have the same length.
• The values in dist are the initial distances of the monsters, and speed represents their constant speed.
• Input: dist = [2,4,6], speed = [2,1,1]
• Explanation: The monsters start at distances [2,4,6] and move at speeds [2,1,1]. We compute the time each monster takes to reach the city, which is [1,4,6]. After eliminating each monster one by one, we find that all 3 can be eliminated before reaching the city.
Approach: The approach involves calculating how long each monster takes to reach the city and sorting the times. We then iterate through the sorted list of times, eliminating monsters one by one until we can no longer eliminate any more.
Observations:
• We can calculate the time for each monster by dividing dist[i] by speed[i].
• After sorting the monsters by their arrival time, we can eliminate monsters in sequence until we hit a monster that arrives before we can eliminate it.
• The solution relies on sorting and then a single scan through the list of monsters, which ensures it runs in O(n log n) time.
Steps:
• Compute the time each monster takes to reach the city.
• Sort the times in ascending order.
• Eliminate monsters one by one until the weapon is not ready before the next monster reaches the city.
Empty Inputs:
• The input will always contain at least one monster.
Large Inputs:
• The solution must handle cases where n is large (up to 10^5).
Special Values:
• If all monsters are close to the city and have high speeds, they may reach the city quickly, limiting how many can be eliminated.
Constraints:
• The algorithm needs to be efficient in both time and space due to the constraints on n.
int eliminateMaximum(vector<int>& dist, vector<int>& speed) {
int n = dist.size();
vector<double> res(n, 0);
for(int i = 0; i < n; i++)
res[i] = (double(dist[i]) / speed[i]);
sort(res.begin(), res.end());
long j = 0, ans = 0;
for (int i = 0; i < n; i++)
if(j < res[i]) {
ans++;
j++;
} else break;
return (int) ans;
}
1 : Function Definition
int eliminateMaximum(vector<int>& dist, vector<int>& speed) {
Defines the function 'eliminateMaximum' which accepts two vectors: 'dist' for distances and 'speed' for speeds, and returns an integer value representing the maximum number of eliminations.
2 : Variable Initialization
int n = dist.size();
Initializes the variable 'n' to store the size of the 'dist' vector.
3 : Array Initialization
vector<double> res(n, 0);
Initializes a vector 'res' of size 'n' to store the calculated times for each element.
4 : Loop Start
for(int i = 0; i < n; i++)
Begins a loop that iterates over each index 'i' of the 'dist' and 'speed' vectors.
5 : Time Calculation
res[i] = (double(dist[i]) / speed[i]);
Calculates the time taken for each element to reach its destination by dividing the distance 'dist[i]' by the speed 'speed[i]', and stores the result in the 'res' vector.
6 : Sorting
sort(res.begin(), res.end());
Sorts the 'res' vector in ascending order to get the fastest times first.
7 : Variable Initialization
long j = 0, ans = 0;
Initializes variables 'j' (the current elimination count) and 'ans' (to store the total number of eliminations).
8 : Loop Start
for (int i = 0; i < n; i++)
Begins another loop to simulate the elimination process using the sorted times from the 'res' vector.
9 : Condition Check
if(j < res[i]) {
Checks if the current elimination count 'j' is less than the corresponding time in the sorted 'res' vector.
10 : Elimination
ans++;
If the condition is met, the elimination count 'ans' is incremented.
11 : Increment
j++;
Increments the elimination index 'j'.
12 : Exit Condition
} else break;
If the condition is not met, the loop breaks, stopping the elimination process.
13 : Return Statement
return (int) ans;
Returns the total number of eliminations as an integer.
Best Case: O(n log n)
Average Case: O(n log n)
Worst Case: O(n log n)
Description: The solution requires sorting the times, which takes O(n log n) time.
Best Case: O(n)
Worst Case: O(n)
Description: We store the computed times for each monster, requiring O(n) space.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus