Eliminate maximum number of monsters

Array Greedy Sorting

51.0% acceptance

Feb 25, 2026

1578

238

You are playing a video game where you are defending your city from a group of n monsters. You are given a 0-indexed integer array dist of size n, where dist[i] is the initial distance in kilometers of the ith monster from the city. The monsters walk toward the city at a constant speed. The speed of each monster is given to you in an integer array speed of size n, where speed[i] is the speed of the ith monster in kilometers per minute. You have a weapon that, once fully charged, can eliminate a single monster. However, the weapon takes one minute to charge. The weapon is fully charged at the very start. You lose when any monster reaches your city. If a monster reaches the city at the exact moment the weapon is fully charged, it counts as a loss, and the game ends before you can use your weapon. Return the maximum number of monsters that you can eliminate before you lose, or n if you can eliminate all the monsters before they reach the city.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn eliminate_maximum(dist: Vec<i32>, speed: Vec<i32>) -> i32 {
    let n = dist.len();
    let mut arrival: Vec<f64> = dist.iter().zip(speed.iter())
      .map(|(&d, &s)| d as f64 / s as f64)
      .collect();
    arrival.sort_by(|a, b| a.partial_cmp(b).unwrap());
    for i in 0..n {
      if arrival[i] <= i as f64 {
        return i as i32;
      }
    }
    n as i32
  }
}