LeetCode 1921: Eliminate Maximum Number of Monsters Solution

Master LeetCode problem 1921 (Eliminate Maximum Number of Monsters), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1921. Eliminate Maximum Number of Monsters

Medium

Array Greedy Sorting

Problem Explanation

Explanation:

To solve this problem, we can simulate the game by keeping track of the time it takes for each monster to reach the city. We can then sort these times and eliminate monsters one by one until we either eliminate all monsters or a monster reaches the city.

Calculate the time each monster takes to reach the city using the formula: time = (dist[i] - 1) / speed[i].
Sort the times in ascending order.
Iterate through the sorted times and eliminate monsters until a monster reaches the city or all monsters are eliminated.

Time Complexity: O(n log n)
Space Complexity: O(n)

Solution Code

class Solution {
    public int eliminateMaximum(int[] dist, int[] speed) {
        int n = dist.length;
        int[] times = new int[n];
        
        for (int i = 0; i < n; i++) {
            times[i] = (dist[i] - 1) / speed[i];
        }
        
        Arrays.sort(times);
        
        int eliminated = 0;
        for (int i = 0; i < n; i++) {
            if (times[i] < i) {
                break;
            }
            eliminated++;
        }
        
        return eliminated;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1921 (Eliminate Maximum Number of Monsters)?

This page provides optimized solutions for LeetCode problem 1921 (Eliminate Maximum Number of Monsters) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1921 (Eliminate Maximum Number of Monsters)?

The time complexity for LeetCode 1921 (Eliminate Maximum Number of Monsters) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1921 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1921 in Java, C++, or Python.

Back to LeetCode Solutions