Eliminate Maximum Number of Monsters

Medium
845.

Eliminate Maximum Number of Monsters

Eliminate Maximum Number of Monsters is a medium coding problem on arrays, sorting and greedy, asked in Amazon, Google and Paytm interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} dist
 * @param {number[]} speed
 * @return {number}
 */
var eliminateMaximum = function(dist, speed) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.length
  • 1 <= n <= 100000
  • 1 <= dist[i], speed[i] <= 100000

Hints for Eliminate Maximum Number of Monsters

  1. Hint 1

    Monster i arrives at time dist[i] / speed[i].

  2. Hint 2

    Shoot in order of arrival time — the soonest first.

  3. Hint 3

    Compare arrival times without division: dist[a] · speed[b] against dist[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

  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

Java

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