2126. Destroying Asteroids

Problem Statement in English

You are given an integer mass representing the mass of a planet and an integer array asteroids where asteroids[i] is the mass of the i-th asteroid.

The planet has to collide with all the asteroids. If the mass of the planet is greater than or equal to the mass of the asteroid, the asteroid is destroyed, and the planet gains the mass of the asteroid. Otherwise, the planet is destroyed. You can rearrange the order of the asteroids.

Return true if all asteroids can be destroyed. Otherwise, return false.

Approach

To solve this problem, we can use a greedy approach.

We want to destroy the asteroids in the order of their mass, starting with the smallest one. This way, we can ensure that we are always destroying the asteroid that has the least mass first, which allows us to gain mass and be able to destroy the next asteroid.

We can sort the array of asteroids and then iterate through it. For each asteroid, we check if the mass of the planet is greater than or equal to the mass of the asteroid. If it is, we destroy the asteroid and add its mass to the planet’s mass. If it is not, we return false because the planet will be destroyed.

And we’re done!

Solution in Python

class Solution:
    def asteroidsDestroyed(self, mass: int, arr: List[int]) -> bool:
        arr.sort()

        for w in arr:
            if mass < w: return False

            mass += w
        
        return True

Complexity

• Time: $O(n \log n)$
  Since we need to sort the array of asteroids.

• Space: $O(1)$
  Since we are sorting the array in place and using only a constant amount of extra space.

And we are done.