Abstract / Summary

You must choose a distance and attacks to eliminate the most monsters by hitting those within that distance each time.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 51% (200k+ submissions).

Typical patterns to solve this problem:

• Array
• Greedy
• Sorting

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided Solution class implements a method eliminateMaximum that determines how many monsters can be eliminated before any of them reaches the city. The method receives two parallel arrays: dist, the initial distances of each monster from the city, and speed, the speed at which each monster approaches. The algorithm converts these inputs into a schedule of deadlines, sorts the deadlines, and then iterates through them to find the first moment a monster would arrive before it can be eliminated. The return value is the count of monsters that can be safely removed.

Key Steps

The first step computes the number of whole minutes each monster has before it reaches the city. This is done with a list comprehension that applies the ceiling division to each pair of distance and speed.

duration = [ ceil(dist[i] / speed[i]) for i in range(n) ]

The second step orders the computed deadlines in ascending order so that monsters with the earliest arrival times are considered first.

for i, d in enumerate(sorted(duration)):

During the iteration, the index i represents the number of monsters already eliminated, while d is the deadline of the current monster. The condition i >= d checks whether the current monster would arrive before the i-th elimination can occur. If the condition holds, the method returns i, which is the maximum number of monsters that can be eliminated safely.

    if i >= d:
        return i

If the loop completes without triggering the early return, it means every monster can be eliminated before reaching the city. In that case, the method returns the total number of monsters.

return n

Edge Cases

The algorithm gracefully handles the situation where a monster is already at the city at time zero. In such a case, dist[i] is zero, the ceiling division yields zero, and the sorted deadlines will contain a zero value. The first iteration will have i == 0 and d == 0, causing the condition i >= d to be true, and the method will correctly return 0, indicating no monster can be eliminated.

When multiple monsters share the same deadline, the sorted list places them consecutively. The iteration checks each one against the increasing index i. If the number of monsters with that deadline exceeds the deadline itself, the early return captures the exact point where elimination becomes impossible.

If the input arrays are empty, n becomes zero, the list comprehension produces an empty list, and the for loop is skipped. The final return statement then yields 0, which correctly reflects that there are no monsters to eliminate.

Performance Optimizations

The use of a list comprehension for the deadline calculation avoids the overhead of an explicit loop and intermediate variable assignments, allowing Python’s internal optimizations for list building to take effect. The ceil function from the math module is applied directly within the comprehension, ensuring that each division result is rounded up in a single operation.

Sorting the duration list is performed once, and the sorted result is consumed directly by the enumerate iterator. This eliminates the need for a separate sorted copy or additional indexing logic. By combining the sorting and iteration in a single for construct, the code minimizes the number of passes over the data.

The early exit condition if i >= d: return i provides a short-circuit mechanism. As soon as a monster cannot be eliminated in time, the method terminates without processing the remaining deadlines. This can significantly reduce runtime for inputs where the failure point occurs early in the sorted order.

Imagine playing a game where little monsters are trying to reach your castle. You have a list of how far away each monster starts and how fast each one can run. First, the computer calculates how many minutes each monster needs to reach the castle by dividing their distance by their speed. Once those times are ready, they are lined up from the fastest monster to the slowest one. A hero then checks the line one by one. If the time it takes for a monster to arrive is smaller than the number of turns taken to defeat them, the monster reaches the gate first. Otherwise, the hero keeps defeating them as long as the monsters have not arrived yet.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: loglinear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Java	Python			TS
	WalkCCC	C++		Java	Python
	leetcode.ca	C++	JS	Java	Python	C#	Go	TS
	Progiez	C++		Java	Python
github	black-shadows	C++
	charles-wangkai			Java
	everthis		JS
	fsq	C++
	JoshCrozier		JS
	lkwq007				Python
	suxrobGM					C#
	varunu28			Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, JavaScript, Python, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
suxrobGM	C#
varunu28	Java

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality