Eliminate Maximum Number of Monsters — Problem & Solution
Eliminate Maximum Number of Monsters solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Eliminate Maximum Number of Monsters is a medium coding problem on arrays, sorting and greedy, asked in Amazon, Google and Paytm interviews.
- Difficulty: Medium
- Topics: Arrays, Sorting, Greedy
- Asked at: Amazon, Google, Paytm
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Monster i starts dist[i] km from your city and closes in at speed[i] km per minute. Your weapon fires instantly at minute 0 and then recharges for one minute, so you can eliminate one monster at minute 0, one at minute 1, and so on.
A monster that reaches the city (distance 0) at or before the minute you would fire counts as a loss, and the game stops immediately. Return the maximum number of monsters you can eliminate.
Example 1
Input: dist = [1,3,4], speed = [1,1,1]
Output: 3
Explanation: They arrive at minutes 1, 3 and 4 — all can be shot in time.
Example 2
Input: dist = [1,1,2,3], speed = [1,1,1,1]
Output: 1
Explanation: Two monsters arrive at minute 1, so one gets through.
Example 3
Input: dist = [3,2,4], speed = [5,3,2]
Output: 1
Explanation: The first two arrive before minute 1.
Constraints
n == dist.length == speed.length1 <= n <= 1000001 <= dist[i], speed[i] <= 100000
Hints for Eliminate Maximum Number of Monsters
Hint 1
Monster
iarrives at timedist[i] / speed[i].Hint 2
Shoot in order of arrival time — the soonest first.
Hint 3
Compare arrival times without division:
dist[a] · speed[b]againstdist[b] · speed[a].
How to solve Eliminate Maximum Number of Monsters
Sort by arrival time and shoot in that order. The i-th shot happens at minute i, so the run ends at the first monster whose arrival time is at or before its own shot minute.
Approach
- Sort the monster indices by
dist[i] / speed[i]ascending, comparing via cross-multiplication. - For the
i-th monster in that order, it is lost ifdist[j] <= i · speed[j]. - Return the index of the first loss, or
nif there is none.
Why it works
Exchange argument: if two monsters are shot out of arrival order, swapping them never makes things worse — the earlier-arriving one gets an earlier shot, and the later one still has slack. So the arrival order is optimal, and the first failure under it is the true answer. Cross-multiplication keeps the comparison exact where floating-point division could tie two distinct arrival times.
Complexity
- Time —
O(n log n) - Space —
O(n)
Pitfalls
dist[a] · speed[b]reaches10^10— the comparison needs 64-bit outside JavaScript.- A monster arriving exactly at its shot minute is a loss, so the test is
<=. - Comparing computed floating-point arrival times can mis-order equal fractions like 2/4 and 1/2.
Reference solution
Python
from typing import List
def eliminateMaximum(dist: List[int], speed: List[int]) -> int:
n = len(dist)
order = sorted(range(n), key=lambda i: dist[i] / speed[i])
for i, j in enumerate(order):
if dist[j] <= i * speed[j]:
return i
return nJava
public static int eliminateMaximum(int[] dist, int[] speed) {
int n = dist.length;
Integer[] idx = new Integer[n];
for (int i = 0; i < n; i++) idx[i] = i;
Arrays.sort(idx, (a, b) -> Long.compare((long) dist[a] * speed[b], (long) dist[b] * speed[a]));
for (int i = 0; i < n; i++) {
int j = idx[i];
if ((long) dist[j] <= (long) i * speed[j]) return i;
}
return n;
}C++
int eliminateMaximum(vector<int>& dist, vector<int>& speed) {
int n = (int) dist.size();
vector<int> idx(n);
for (int i = 0; i < n; i++) idx[i] = i;
sort(idx.begin(), idx.end(), [&](int a, int b) {
return (long long) dist[a] * speed[b] < (long long) dist[b] * speed[a];
});
for (int i = 0; i < n; i++) {
int j = idx[i];
if ((long long) dist[j] <= (long long) i * speed[j]) return i;
}
return n;
}JavaScript
var eliminateMaximum = function(dist, speed) {
var n = dist.length;
var idx = [];
for (var t = 0; t < n; t++) idx.push(t);
idx.sort(function(a, b) { return dist[a] * speed[b] - dist[b] * speed[a]; });
for (var i = 0; i < n; i++) {
var j = idx[i];
if (dist[j] <= i * speed[j]) return i;
}
return n;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms