{x}
blog image

Destroying Asteroids

You are given an integer mass, which represents the original mass of a planet. You are further given an integer array asteroids, where asteroids[i] is the mass of the ith asteroid.

You can arrange for the planet to collide with the asteroids in any arbitrary order. 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.

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

 

Example 1:

Input: mass = 10, asteroids = [3,9,19,5,21]
Output: true
Explanation: 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
Explanation: 
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 Explanation:

The problem asks whether a planet can destroy all asteroids given its initial mass and the masses of the asteroids. The planet can destroy an asteroid if its mass is greater than or equal to the asteroid's mass. After destroying an asteroid, the planet gains the asteroid's mass. The asteroids can be destroyed in any order.

The key insight is that the order in which we destroy the asteroids matters. To guarantee we can destroy all asteroids, we should destroy them in increasing order of their mass. This greedy approach ensures that the planet's mass grows as quickly as possible, increasing the chances of destroying larger asteroids later.

Algorithm:

  1. Sort the asteroids: Sort the asteroids array in ascending order of their mass. This allows us to process the smaller asteroids first.
  2. Iterate and destroy: Iterate through the sorted asteroids array. For each asteroid:
    • Check if the planet's current mass (mass) is greater than or equal to the asteroid's mass (v). If not, the planet cannot destroy this asteroid and we return false.
    • If the planet can destroy the asteroid, add the asteroid's mass to the planet's mass (mass += v).
  3. Return True: If the loop completes without returning false, it means the planet could destroy all asteroids, so we return true.

Time Complexity: O(N log N), dominated by the sorting of the asteroids array, where N is the number of asteroids.

Space Complexity: O(1) or O(log N) depending on the sorting algorithm used. In-place sorting algorithms like merge sort or heap sort use O(log N) space for recursion. Some implementations may use O(N) extra space if they copy the array before sorting.

Code Explanation (Python):

class Solution:
    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:
        asteroids.sort()  # Sort asteroids in ascending order
        for v in asteroids:
            if mass < v:  # Check if planet can destroy asteroid
                return False  # If not, return False
            mass += v  # Increase planet mass after destruction
        return True  # All asteroids destroyed

The Java, C++, Go and TypeScript code follow the same logic, only differing in syntax. The use of long in Java and long long in C++ is to prevent potential integer overflow when summing the masses, especially when dealing with a large number of asteroids with significant masses. Note that in Python this isn't needed because Python integers handle arbitrary precision.