#2126

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Destroying Asteroids

This problem requires destroying asteroids by choosing the right order of collisions based on mass, using a greedy approach.

array greedy sorting

Problem Statement

You are given an integer mass representing the mass of a planet. You are also given an array of integers asteroids, where each element represents the mass of an asteroid. You must determine if the planet can destroy all asteroids based on its mass and the order in which the asteroids collide with it.

The planet can destroy an asteroid if its mass is greater than or equal to the mass of the asteroid. After each successful collision, the planet's mass increases by the mass of the destroyed asteroid. If at any point, the planet’s mass is smaller than an asteroid's mass, the planet will be destroyed. Return true if all asteroids can be destroyed, otherwise return false.

Examples

Example 1

Input: mass = 10, asteroids = [3,9,19,5,21]

Output: true

One way to order the asteroids is [9,19,5,3,21]:

The planet collides with the asteroid with a mass of 9. New planet mass: 10 + 9 = 19
The planet collides with the asteroid with a mass of 19. New planet mass: 19 + 19 = 38
The planet collides with the asteroid with a mass of 5. New planet mass: 38 + 5 = 43
The planet collides with the asteroid with a mass of 3. New planet mass: 43 + 3 = 46
The planet collides with the asteroid with a mass of 21. New planet mass: 46 + 21 = 67 All asteroids are destroyed.

Example 2

Input: mass = 5, asteroids = [4,9,23,4]

Output: false

The planet cannot ever gain enough mass to destroy the asteroid with a mass of 23. After the planet destroys the other asteroids, it will have a mass of 5 + 4 + 9 + 4 = 22. This is less than 23, so a collision would not destroy the last asteroid.

Constraints

1 <= mass <= 105
1 <= asteroids.length <= 105
1 <= asteroids[i] <= 105

Solution Approach

Greedy Selection of Asteroids

The solution relies on selecting the asteroids to collide with based on their mass. A greedy approach suggests that you should always collide with the smallest asteroid that the planet can destroy, ensuring it grows in mass as much as possible before facing larger asteroids. Sorting the asteroids array in ascending order allows for a straightforward approach.

Simulate the Collisions

After sorting the asteroids, iterate through the sorted list and check if the planet's mass is sufficient to destroy each asteroid. For each asteroid, if the planet’s mass is greater than or equal to the asteroid's mass, it destroys the asteroid and gains its mass. If the planet cannot destroy an asteroid, return false.

Early Termination for Efficiency

To optimize, the process should terminate early once the planet encounters an asteroid it cannot destroy. This prevents unnecessary checks for the remaining asteroids, improving efficiency.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of the solution is dominated by the sorting step, which is O(n log n), where n is the number of asteroids. The space complexity is O(n) due to the space required for sorting the asteroid array.

What Interviewers Usually Probe

The candidate is expected to grasp the greedy approach and its application to the problem.
They should be able to justify why sorting the array helps simplify the solution.
The interviewer may want to see how the candidate handles early termination to improve efficiency.

Common Pitfalls or Variants

Common pitfalls

A common mistake is not sorting the asteroids first, which leads to suboptimal solutions and increased complexity.
Failing to handle edge cases, such as the planet having insufficient mass to destroy the largest asteroid, can result in incorrect answers.
Misunderstanding the greedy approach may lead to choosing asteroids in the wrong order, causing the planet to be destroyed prematurely.

Follow-up variants

What if the planet has a fixed number of asteroid collisions allowed? The problem could be adjusted to account for a limited number of successful collisions.
What if asteroids can be destroyed in any order, not just by increasing mass? This would remove the greedy choice pattern and require a different approach.
What if there are multiple planets with different masses trying to destroy the same asteroids? This could require a more complex simulation with multiple greedy selections.

FAQ

What is the main pattern used in the 'Destroying Asteroids' problem?

The main pattern used in the 'Destroying Asteroids' problem is a greedy approach, where you select the smallest asteroid that can be destroyed to maximize the planet's growth in mass.

Can the asteroids be destroyed in any order?

No, the asteroids must be destroyed in an order where the planet’s mass is greater than or equal to the asteroid's mass at every step. Sorting the asteroids helps with this.

What is the optimal way to approach the 'Destroying Asteroids' problem?

The optimal way is to sort the asteroids in increasing order and then check if the planet’s mass is sufficient to destroy each asteroid, updating the planet’s mass accordingly.

How does GhostInterview assist with solving the 'Destroying Asteroids' problem?

GhostInterview helps by providing step-by-step guidance on the greedy approach and optimizing the solution with early termination for better performance.

What are common mistakes when solving the 'Destroying Asteroids' problem?

Common mistakes include not sorting the asteroids, failing to handle edge cases, and not correctly applying the greedy approach for optimal asteroid selection.

terminal

Solution

Solution 1: Sorting + Greedy

According to the problem description, we can sort the asteroids by mass in ascending order, and then iterate through the asteroids. If the planet's mass is less than the asteroid's mass, the planet will be destroyed, and we return `false`. Otherwise, the planet will gain the mass of the asteroid.

1

2

3

4

5

6

7

8

class Solution:
    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:
        asteroids.sort()
        for x in asteroids:
            if mass < x:
                return False
            mass += x
        return True

Continue Practicing

#2136 earliest possible day of full bloom #2141 maximum running time of n computers #2144 minimum cost of buying candies with discount