Problem Description

You're defending a city from n monsters in a video game. Each monster starts at a certain distance from the city and walks toward it at a constant speed.

Given:

• dist[i]: the initial distance (in kilometers) of the i-th monster from the city
• speed[i]: the speed (in kilometers per minute) of the i-th monster

You have a weapon that can eliminate one monster at a time, but it takes exactly one minute to charge between shots. The weapon starts fully charged at the beginning of the game.

Important rules:

• You can only eliminate one monster per minute
• The weapon needs one full minute to recharge after each use
• You lose if any monster reaches the city
• If a monster arrives at the exact moment your weapon becomes ready, you still lose (the monster reaches the city before you can shoot)

Your goal is to find the maximum number of monsters you can eliminate before losing the game. If you can eliminate all n monsters before any reach the city, return n.

The strategy involves calculating when each monster would reach the city and determining how many you can eliminate in time. For each monster, you need to calculate the latest moment you can eliminate it (just before it reaches the city), then greedily eliminate monsters in the order that gives you the most eliminations possible.

The key insight is that the latest safe elimination time for monster i is ⌊(dist[i] - 1) / speed[i]⌋ minutes (using floor division to get whole minutes). By sorting these times and checking if you have enough time to eliminate each monster in sequence, you can determine the maximum number of eliminations possible.

Intuition

Think about what happens in this game: you can shoot exactly one monster per minute, starting at minute 0. So at minute 0 you shoot the first monster, at minute 1 you shoot the second monster, and so on.

The critical question is: which monsters should we shoot and in what order?

First, let's figure out when each monster becomes a threat. A monster at distance dist[i] moving at speed speed[i] will reach the city at time dist[i] / speed[i]. But we need to eliminate it before it reaches the city. Since we're dealing with discrete minutes, the latest minute we can eliminate this monster is ⌊(dist[i] - 1) / speed[i]⌋.

Why (dist[i] - 1)? Because if a monster is at distance 5 and speed 1, it reaches at minute 5. We need to shoot it by minute 4 at the latest. Using (5-1)/1 = 4 gives us this deadline correctly.

Now comes the key insight: we should eliminate monsters in order of their deadlines. Why? Because:

• At minute 0, we must shoot some monster
• At minute 1, we must shoot another monster
• And so on...

If we have the deadlines sorted, we can check:

• Can we shoot monster 0 at minute 0? (Is its deadline >= 0?)
• Can we shoot monster 1 at minute 1? (Is its deadline >= 1?)
• Can we shoot monster 2 at minute 2? (Is its deadline >= 2?)

The greedy approach works because once we've sorted by deadlines, shooting the monsters with earlier deadlines first ensures we don't miss any opportunity. If a monster's deadline is less than the minute we'd shoot it (its index in the sorted order), then we can't eliminate it in time, and that's where we stop.

This transforms the problem from "which monsters to shoot and when" into a simple check: after sorting by deadlines, does each monster's deadline allow us to shoot it at its position in the queue?

Learn more about Greedy and Sorting patterns.

Solution Approach

Following our intuition, let's implement the solution step by step:

Step 1: Calculate elimination deadlines

For each monster, we calculate the latest minute at which we can eliminate it:

times = sorted((d - 1) // s for d, s in zip(dist, speed))

This line does several things:

• zip(dist, speed) pairs up each monster's distance with its speed
• For each pair (d, s), we calculate (d - 1) // s using integer division
• The (d - 1) ensures we get the last full minute before the monster arrives
• We sort these deadlines in ascending order

Step 2: Check if we can eliminate monsters in order

for i, t in enumerate(times):
    if t < i:
        return i
return len(times)

This greedy validation works as follows:

• We iterate through the sorted deadlines with their indices
• At minute i, we attempt to eliminate the i-th monster (0-indexed)
• If times[i] < i, it means the monster's deadline is before minute i
  • The monster would reach the city before we can shoot it
  • We return i as the maximum number of monsters we can eliminate
• If we successfully check all monsters without returning early, it means we can eliminate all n monsters

Example walkthrough:

Let's say dist = [3, 5, 7] and speed = [1, 1, 2]:

• Monster 0: deadline = (3-1)//1 = 2
• Monster 1: deadline = (5-1)//1 = 4
• Monster 2: deadline = (7-1)//2 = 3

After sorting: times = [2, 3, 4]

Checking:

• Minute 0: Can we shoot monster with deadline 2? Yes (2 >= 0) ✓
• Minute 1: Can we shoot monster with deadline 3? Yes (3 >= 1) ✓
• Minute 2: Can we shoot monster with deadline 4? Yes (4 >= 2) ✓

Result: We can eliminate all 3 monsters.

The algorithm has a time complexity of O(n log n) due to sorting, and space complexity of O(n) for storing the deadlines.

Example Walkthrough

Let's walk through a concrete example to see how the solution works:

Example: dist = [4, 2, 8], speed = [2, 1, 2]

Step 1: Calculate elimination deadlines for each monster

• Monster 0: distance = 4, speed = 2

  • Arrival time: 4/2 = 2 minutes
  • Latest elimination time: (4-1)//2 = 3//2 = 1 minute

• Monster 1: distance = 2, speed = 1

  • Arrival time: 2/1 = 2 minutes
  • Latest elimination time: (2-1)//1 = 1//1 = 1 minute

• Monster 2: distance = 8, speed = 2

  • Arrival time: 8/2 = 4 minutes
  • Latest elimination time: (8-1)//2 = 7//2 = 3 minutes

Step 2: Sort the deadlines

Deadlines: [1, 1, 3] → Already sorted in this case

Step 3: Check if we can eliminate each monster at its scheduled minute

• Minute 0: Try to eliminate first monster (deadline = 1)

  • Can we shoot it at minute 0? Check: 1 >= 0? ✓ Yes

• Minute 1: Try to eliminate second monster (deadline = 1)

  • Can we shoot it at minute 1? Check: 1 >= 1? ✓ Yes

• Minute 2: Try to eliminate third monster (deadline = 3)

  • Can we shoot it at minute 2? Check: 3 >= 2? ✓ Yes

Result: We can eliminate all 3 monsters!

Counter-example to show when we can't eliminate all:

dist = [1, 1, 3], speed = [1, 1, 1]

• Monster 0: (1-1)//1 = 0 (must shoot at minute 0)
• Monster 1: (1-1)//1 = 0 (must shoot at minute 0)
• Monster 2: (3-1)//1 = 2 (must shoot by minute 2)

Sorted deadlines: [0, 0, 2]

Checking:

• Minute 0: deadline 0 >= 0? ✓ Yes
• Minute 1: deadline 0 >= 1? ✗ No! (0 < 1)

We can only eliminate 1 monster before losing the game.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n)

The time complexity is dominated by the sorting operation. Breaking down the algorithm:

• Creating the times list using list comprehension with zip: O(n), where n is the length of the input arrays
• Sorting the times list: O(n × log n)
• Iterating through the sorted list with enumerate: O(n)

The overall time complexity is O(n) + O(n × log n) + O(n) = O(n × log n).

Space Complexity: O(n)

The space complexity analysis:

• The times list stores n elements (arrival times for each monster): O(n)
• The sorting operation may use additional space depending on the implementation (Python's Timsort uses up to O(n) auxiliary space in worst case)
• The enumerate iterator and loop variables use constant space: O(1)

Therefore, the total space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Arrival Time Calculation

The Pitfall: A common mistake is calculating the arrival time as simply dist[i] / speed[i] or dist[i] // speed[i]. This fails to account for the edge case where a monster arrives at the exact moment your weapon becomes ready.

Why it's wrong:

• If a monster arrives at exactly minute 3.0, and your weapon becomes ready at minute 3.0, the monster reaches the city before you can shoot
• Using dist[i] // speed[i] would suggest you can eliminate it at minute 3, but that's too late

The Solution: Use (dist[i] - 1) // speed[i] to get the last safe minute to eliminate the monster. This ensures you shoot before the monster arrives.

# Wrong
arrival_times = sorted(dist[i] // speed[i] for i in range(len(dist)))

# Correct
arrival_times = sorted((dist[i] - 1) // speed[i] for i in range(len(dist)))

2. Not Sorting the Arrival Times

The Pitfall: Processing monsters in their original order instead of by urgency (arrival time).

Why it's wrong: You might waste early shots on monsters that arrive later, missing the opportunity to eliminate more urgent threats.

Example:

• Monster A: arrives at minute 5
• Monster B: arrives at minute 1
• If you shoot A first (minute 0), B reaches the city at minute 1 before you can shoot again

The Solution: Always sort monsters by their arrival deadlines to prioritize the most urgent threats first.

3. Off-by-One Error in Elimination Check

The Pitfall: Using <= instead of < when checking if we can eliminate a monster in time.

# Wrong - this would allow shooting after the monster arrives
if arrival_time <= minute:
    return minute

# Correct - we can only shoot if the monster hasn't arrived yet
if arrival_time < minute:
    return minute

Why it matters: At minute i, we're about to shoot our (i+1)-th monster. If the monster's deadline equals i, it means the monster arrives exactly when we're trying to shoot, which is too late.

4. Using Floating-Point Division

The Pitfall: Using regular division / instead of integer division // can lead to floating-point precision issues.

# Potentially problematic with floating-point arithmetic
arrival_time = int((dist[i] - 1) / speed[i])

# Better - uses integer division directly
arrival_time = (dist[i] - 1) // speed[i]

The Solution: Stick to integer division // to avoid any floating-point precision errors and ensure consistent results.