Eliminate Maximum Number of Monsters - Practice Coding Problems

Eliminate Maximum Number of Monsters - Problem

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 i^th 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 i^th 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.

Input & Output

Example 1 — Basic Case

$ Input: dist = [1,3,4], speed = [1,1,1]

› Output: 2

💡 Note: Monster 0 arrives at time 1, Monster 1 at time 3, Monster 2 at time 4. We can eliminate Monster 0 at time 0→1, Monster 1 at time 1→2. Monster 2 would arrive at time 4, but we can't charge until time 3, so we can eliminate it at time 2→3. Actually, we eliminate 2 monsters before losing.

Example 2 — All Monsters Eliminated

$ Input: dist = [3,2,4], speed = [5,3,2]

› Output: 3

💡 Note: Arrival times: Monster 0 at 0.6min, Monster 1 at 0.67min, Monster 2 at 2min. We eliminate Monster 0 at time 0→1, Monster 1 at time 1→2, Monster 2 at time 2→3. All monsters eliminated before they reach the city.

Example 3 — Early Arrival

$ Input: dist = [4,2,3], speed = [2,1,1]

› Output: 2

💡 Note: Arrival times: Monster 0 at 2min, Monster 1 at 2min, Monster 2 at 3min. We can eliminate Monster 0 at time 0→1 and Monster 1 at time 1→2, but Monster 2 arrives at time 3 which equals our charge time, so we lose before eliminating it.

Constraints

n == dist.length == speed.length
1 ≤ n ≤ 10⁵
1 ≤ dist[i], speed[i] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input

Monsters at different distances with different speeds

Strategy

Calculate arrival times and prioritize most urgent

Output

Maximum monsters eliminated before losing

Key Takeaway

🎯 Key Insight: Always eliminate the monster that will arrive soonest to maximize survival time

Asked in

G Google 15 a Amazon 12 M Microsoft 8 A Apple 6

The key insight is that we should always eliminate the monster that will arrive soonest to maximize our survival time. The optimal approach uses a greedy strategy: calculate each monster's arrival time (distance/speed), sort by arrival time, then eliminate monsters in that order until one arrives before we can charge our weapon. Time: O(n log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Orders	O(n!)	O(n)	Try all possible orders of eliminating monsters to find the maximum
Greedy - Eliminate Most Urgent First	O(n log n)	O(n)	Always eliminate the monster that will arrive at the city soonest

Brute Force - Try All Orders — Algorithm Steps

Generate all possible elimination orders
For each order, simulate elimination process
Track maximum monsters eliminated across all orders

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Orders

Create all possible elimination sequences

Simulate Each

Test each order and count eliminations

Find Maximum

Return the best result found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* dist, int distSize, int* speed, int speedSize) {
    // Simplified brute force approach
    int maxEliminated = 0;
    
    // Try eliminating monsters in order of arrival time
    for (int eliminated = 0; eliminated <= distSize; eliminated++) {
        double time = 0;
        int count = 0;
        int used[1000] = {0}; // Assuming max 1000 monsters
        
        for (int round = 0; round < eliminated && round < distSize; round++) {
            int bestIdx = -1;
            double earliestArrival = 1e9;
            
            // Find monster that arrives earliest
            for (int i = 0; i < distSize; i++) {
                if (!used[i]) {
                    double arrivalTime = (double)dist[i] / speed[i];
                    if (arrivalTime < earliestArrival) {
                        earliestArrival = arrivalTime;
                        bestIdx = i;
                    }
                }
            }
            
            if (bestIdx != -1 && earliestArrival > time) {
                used[bestIdx] = 1;
                count++;
                time += 1.0;
            } else {
                break;
            }
        }
        
        if (count > maxEliminated) {
            maxEliminated = count;
        }
        if (count < eliminated) break;
    }
    
    return maxEliminated;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse dist array
    int dist[1000];
    int distSize = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (token[0] >= '0' && token[0] <= '9') {
            dist[distSize++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    fgets(line, sizeof(line), stdin);
    int speed[1000];
    int speedSize = 0;
    token = strtok(line, "[,]");
    while (token != NULL) {
        if (token[0] >= '0' && token[0] <= '9') {
            speed[speedSize++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    printf("%d\n", solution(dist, distSize, speed, speedSize));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n!)

Generate all n! permutations and simulate each one

⚠ Quadratic Growth

Space Complexity

O(n)

Store current permutation and monster states

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Orders — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler