We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Eliminate Maximum Number of Monsters

Number: 2049

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

You are given two arrays, dist and speed, where dist[i] is the initial distance of the iᵗʰ monster from your city and speed[i] is its speed (in km/min). Your weapon is initially charged and can eliminate one monster per minute (after which it needs one minute to recharge). However, if a monster reaches your city (or arrives exactly when your weapon finishes recharging), you lose. The goal is to determine the maximum number of monsters you can eliminate before any one reaches the city, or eliminate all monsters if possible.

Key Insights

  • Compute each monster's arrival time as dist[i] / speed[i].
  • Sort the arrival times in ascending order.
  • Use a greedy strategy: at minute i, eliminate the monster with the smallest arrival time.
  • If the monster's arrival time is less than or equal to the current minute, then it reaches the city before you can eliminate it.
  • Continue until you can no longer eliminate a monster before it arrives.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting. Space Complexity: O(n) to store the computed arrival times.

Solution

We first calculate the time each monster will reach the city by dividing its distance by its speed. We then sort these times. Starting from minute 0, we simulate the elimination of one monster per minute. If at the current minute the next monster's arrival time is less than or equal to the minute, it means that monster has reached the city, and the game is over. Otherwise, we successfully eliminate the monster and move to the next minute. The process continues until we either run out of monsters or encounter a monster whose arrival time is too soon.

Code Solutions

class Solution:
    def eliminateMaximum(self, dist, speed):
        # Calculate the time each monster will reach the city.
        arrival_times = [d / s for d, s in zip(dist, speed)]
        
        # Sort the arrival times in ascending order.
        arrival_times.sort()
        
        # For each minute, eliminate a monster.
        for minute, arrival in enumerate(arrival_times):
            # If the monster arrives before or exactly at the current minute, you lose.
            if arrival <= minute:
                return minute
        return len(arrival_times)

# Example usage:
# sol = Solution()
# print(sol.eliminateMaximum([1,3,4], [1,1,1]))  # Expected output: 3
← Back to All Questions