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 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.

Examples

Example 1:

1
2
3
4
5
6
7

Input: dist = [1,3,4], speed = [1,1,1]
Output: 3
Explanation:
In the beginning, the distances of the monsters are [1,3,4]. You eliminate the first monster.
After a minute, the distances of the monsters are [X,2,3]. You eliminate the second monster.
After a minute, the distances of the monsters are [X,X,2]. You eliminate the thrid monster.
All 3 monsters can be eliminated.

Example 2:

1
2
3
4
5
6

Input: dist = [1,1,2,3], speed = [1,1,1,1]
Output: 1
Explanation:
In the beginning, the distances of the monsters are [1,1,2,3]. You eliminate the first monster.
After a minute, the distances of the monsters are [X,0,1,2], so you lose.
You can only eliminate 1 monster.

Example 3:

1
2
3
4
5
6

Input: dist = [3,2,4], speed = [5,3,2]
Output: 1
Explanation:
In the beginning, the distances of the monsters are [3,2,4]. You eliminate the first monster.
After a minute, the distances of the monsters are [X,0,2], so you lose.
You can only eliminate 1 monster.

Solution

Method 1 - Sorting and Greedy

We first compute the time each monster takes to reach the city and store these as their arrival times, then sort this array.

At each minute, we eliminate the monster with the earliest arrival; if a monster arrives before it can be eliminated, we stop. For example, with arrival = [1,3,4], the monster at index 0 must be eliminated first since it arrives soonest.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    int eliminateMaximum(vector<int>& dist, vector<int>& speed) {
        int n = dist.size();
        vector<int> arrival(n);
        for (int i = 0; i < n; ++i) {
            arrival[i] = (dist[i] + speed[i] - 1) / speed[i]; // ceil division
        }
        sort(arrival.begin(), arrival.end());
        int eliminated = 0;
        for (int i = 0; i < n; ++i) {
            if (arrival[i] > i) {
                ++eliminated;
            } else {
                break;
            }
        }
        return eliminated;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

func eliminateMaximum(dist []int, speed []int) int {
    n := len(dist)
    arrival := make([]int, n)
    for i := 0; i < n; i++ {
        arrival[i] = (dist[i] + speed[i] - 1) / speed[i] // ceil division
    }
    sort.Ints(arrival)
    eliminated := 0
    for i := 0; i < n; i++ {
        if arrival[i] > i {
            eliminated++
        } else {
            break
        }
    }
    return eliminated
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
	public int eliminateMaximum(int[] dist, int[] speed) {
		int n = dist.length;
		int[] arrival = new int[n];
	
		for(int i = 0; i < n; i++){
			arrival[i] = (int)Math.ceil(dist[i] * 1.0 / speed[i]);
		}
		
		Arrays.sort(arrival);
		
		int eliminated = 0;
		
		// At i = 0, minute = 0 ( therefore, we can use i in place of minute )
		
		for(int i = 0; i < n; i++){
			// if current arrival time is more than current minute, 
			// eliminate the monstor 
			if(arrival[i] > i){
				eliminated++;
			}else{
				break; // Monster reached the city
			}
		}
		
		return eliminated;
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    fun eliminateMaximum(dist: IntArray, speed: IntArray): Int {
        val n = dist.size
        val arrival = IntArray(n) { i -> (dist[i] + speed[i] - 1) / speed[i] }
        arrival.sort()
        var eliminated = 0
        for (i in 0 until n) {
            if (arrival[i] > i) {
                eliminated++
            } else {
                break
            }
        }
        return eliminated
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:
        n = len(dist)
        arrival = [(dist[i] + speed[i] - 1) // speed[i] for i in range(n)]  # ceil division
        arrival.sort()
        eliminated = 0
        for i in range(n):
            if arrival[i] > i:
                eliminated += 1
            else:
                break
        return eliminated
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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

Complexity

  • ⏰ Time complexity: O(n log n)
  • 🧺 Space complexity: O(1)

Method 2 - Using minHeap

Compute when each monster will arrive at the city, then use a min-heap to always eliminate the monster with the earliest arrival each minute, stopping if a monster reaches the city before it can be eliminated.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    int eliminateMaximum(vector<int>& dist, vector<int>& speed) {
        priority_queue<double, vector<double>, greater<double>> minHeap;
        for (int i = 0; i < dist.size(); ++i) {
            minHeap.push((double)dist[i] / speed[i]);
        }
        double min = 0.0;
        int count = 0;
        while (!minHeap.empty() && minHeap.top() > min) {
            min += 1.0;
            minHeap.pop();
            count++;
        }
        return count;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

type Float64Heap []float64

func (h Float64Heap) Len() int           { return len(h) }
func (h Float64Heap) Less(i, j int) bool { return h[i] < h[j] }
func (h Float64Heap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *Float64Heap) Push(x interface{}) { *h = append(*h, x.(float64)) }
func (h *Float64Heap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

func eliminateMaximum(dist []int, speed []int) int {
    h := &Float64Heap{}
    heap.Init(h)
    for i := 0; i < len(dist); i++ {
        heap.Push(h, float64(dist[i])/float64(speed[i]))
    }
    min := 0.0
    count := 0
    for h.Len() > 0 && (*h)[0] > min {
        heap.Pop(h)
        min += 1.0
        count++
    }
    return count
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
	public int eliminateMaximum(int[] dist, int[] speed) {
		PriorityQueue<Double> minHeap = new PriorityQueue<>();
		for (int i = 0; i < dist.length; i++) {
			minHeap.add(dist[i] * 1.0 / speed[i]);
		}
		
		double min = 0.0;
		int count = 0;
		while (!minHeap.isEmpty() && minHeap.poll() > min) {
			min += 1.0;
			count++;
		}
		
		return count;
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    fun eliminateMaximum(dist: IntArray, speed: IntArray): Int {
        val minHeap = PriorityQueue<Double>()
        for (i in dist.indices) {
            minHeap.add(dist[i].toDouble() / speed[i])
        }
        var min = 0.0
        var count = 0
        while (minHeap.isNotEmpty() && minHeap.peek() > min) {
            min += 1.0
            minHeap.poll()
            count++
        }
        return count
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:
        min_heap = [d / s for d, s in zip(dist, speed)]
        heapq.heapify(min_heap)
        min_time = 0.0
        count = 0
        while min_heap and min_heap[0] > min_time:
            heapq.heappop(min_heap)
            min_time += 1.0
            count += 1
        return count
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

impl Solution {
    pub fn eliminate_maximum(dist: Vec<i32>, speed: Vec<i32>) -> i32 {
        let mut heap: Vec<f64> = dist.iter().zip(speed.iter())
            .map(|(&d, &s)| d as f64 / s as f64)
            .collect();
        heap.sort_by(|a, b| a.partial_cmp(b).unwrap());
        let mut min = 0.0;
        let mut count = 0;
        for &time in &heap {
            if time > min {
                min += 1.0;
                count += 1;
            } else {
                break;
            }
        }
        count
    }
}

Complexity

  • ⏰ Time complexity: O(n log n)
  • 🧺 Space complexity: O(n)