Problem Statement in English

You’re given two lists of integers dist and speed. dist[i] describes the distance between the i-th monster and the city. speed[i] describes the speed of the i-th monster.

You have to eliminate as many monsters as possible before they reach the city. Return the maximum number of monsters that can be eliminated.

Approach

If you think about it, you must prioritise the elimination of monsters depending on the time they take to reach the city. The monster that takes the least time to reach the city must be eliminated first. This is because the monster that takes the least time to reach the city will reach the city first.

So all we really need to do is calculate the time taken by each monster to reach the city and sort them in ascending order. Then we can iterate through the sorted list and greedily eliminate the monsters one by one.

Solution in Python


class Solution:
    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:
        times = []
        l = len(dist)

        for i in range(l):
            times.append(dist[i]/speed[i])

        times.sort()

        curr_time = 0
        res = 0

        for time in times:
            if curr_time < time:
                res+=1
                curr_time+=1
            else:
                return res
        return l

Complexity

  • Time: O(nlogn)O(nlogn)
    Since we are sorting the list of times, the time complexity is O(nlogn)O(nlogn)

  • Space: O(1)O(1)
    Since we don’t use any extra space, the space complexity is O(1)O(1)

And we are done.