Get started

Eliminate Maximum Number of Monsters — Medium Problem & Solution

Monster i starts dist[i] km from your city and closes in at speed[i] km per minute.

  • Difficulty: Medium
  • Topics: Arrays, Greedy, Sorting
  • 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.length
  • 1 <= n <= 100000
  • 1 <= dist[i], speed[i] <= 100000

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

  1. Sort the monster indices by dist[i] / speed[i] ascending, comparing via cross-multiplication.
  2. For the i-th monster in that order, it is lost if dist[j] <= i · speed[j].
  3. Return the index of the first loss, or n if 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] reaches 10^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 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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue