Eliminate Maximum Number Of Monsters - Leetcode Solution

Problem Statement: Given an array of integers representing the positions of monsters in a 1-D universe, and an integer representing the maximum distance a player can travel in one move. We need to eliminate the maximum possible number of monsters, and return the number of monsters eliminated.

Solution: To eliminate most number of monsters, the first step is to sort the array in ascending order. Now we can start from 0th index, and try to eliminate the next most dangerous monster within player’s reach.

For each monster, we check if the distance between previous elimination and the current monster's position is less than or equal to the maximum distance the player can move in one move. If the distance is less than or equal to the maximum distance, we mark this monster as eliminated and continue our search for the next most dangerous monster within player’s reach. If the distance between the previous elimination and the current monster's position is greater than the maximum distance, we skip this monster and move on to the next one.

We continue this until we reach the end of the array. We count the number of eliminated monsters and return it as the result.

Here is the pseudocode for the solution:

1. Sort the array in ascending order
2. Initialize variables: a. prev_eliminated = -1 b. monsters_eliminated = 0
3. For i = 0 to n-1: a. If the distance between prev_eliminated and a[i] <= max_distance: i. Increment monsters_eliminated ii. Set prev_eliminated = a[i] b. If the distance between prev_eliminated and a[i] > max_distance: i. Move to next monster
4. Return monsters_eliminated

Time Complexity: The time complexity of the solution is O(nlogn) due to the sorting operation. The for loop runs for n elements, therefore the overall time complexity is O(nlogn + n) = O(nlogn).

Space Complexity: The space complexity is O(1) as we are only using a few constant sized variables. It does not depend upon the input size.

Conclusion: In this problem, we learned how to eliminate the maximum possible number of monsters by starting from the least dangerous monsters and eliminating the closest monster within player’s reach. Sorting the array in advance was essential to achieve this. This approach had a time complexity of O(nlogn) which is quite efficient.

1