2126. Destroying Asteroids

Problem Description

In this problem, we're dealing with a scenario where you have a planet with a given mass and a sequence of asteroids, each with their own mass. The crux of the problem is to determine whether the planet can survive collisions with all of the asteroids, one by one, in any order of our choosing. When a collision with an asteroid occurs, if the planet’s mass is at least as much as that asteroid, the asteroid gets destroyed, and the planet absorbs its mass, becoming more massive. However, if the asteroid's mass is greater, the planet would be destroyed upon impact. Our task is to decide whether we can find a sequence in which all asteroids can be destroyed by the planet without the planet being destroyed in the process.

Intuition

To solve this problem, we focus on a greedy strategy. The intuition here is quite simple: start with the smallest asteroid. If the planet can't destroy the smallest asteroid, there is no way it can destroy the larger ones. Because collisions are not sequence specific, we can tackle asteroids in ascending order of mass without impacting the overall outcome.

Following this strategy, we should first sort the asteroids by their mass in ascending order. Then, we iterate through the sorted list, at each step checking if the planet's mass is sufficient to destroy the current asteroid. If it is, we add this asteroid's mass to the planet, effectively increasing its ability to destroy subsequent, possibly larger asteroids. If, at any point, we encounter an asteroid that is too big to be destroyed (i.e., its mass is greater than the planet's current mass), we know that the sequence in which the rest of the collisions occur is irrelevant — the planet simply can't destroy all of the asteroids.

Here's the reasoning in steps:

Sort asteroids in increasing order to prioritize absorbing smaller asteroids first.
For each asteroid in the sorted asteroids:
- If the planet's mass is less than the current asteroid's mass, return False as the planet will be destroyed.
- If the planet's mass is greater or equal to the asteroid's mass, add the asteroid's mass to the planet's mass.
If all asteroids are successfully absorbed, return True.

The solution provided confirms to this approach, ensuring the planet's survival is determined optimally.

Learn more about Greedy and Sorting patterns.

Solution Approach

The implementation of the proposed solution takes advantage of a very simple yet effective idea from the field of algorithms — specifically, a greedy strategy requires sorting to work correctly.

Here are the steps involved in implementing the solution:

The asteroids array is sorted using Python's built-in .sort() method, which sorts the array in-place in ascending order. Sorting is essential because it allows us to begin absorbing asteroids from smallest to largest, therefore ensuring the planet accumulates as much mass as possible before encountering larger asteroids.
A for loop is then used to iterate over the sorted asteroids. The for loop checks each asteroid's mass against the current mass of the planet.
Inside the loop, there's an if statement that checks whether the current asteroid's mass is greater than the planet's mass. If that's the case (mass < v), then it's not possible for the planet to survive the collision with this asteroid, and the function immediately returns False.
If the planet's mass is sufficient to destroy the asteroid (mass >= v), it absorbs the asteroid's mass (mass += v). The planet's mass is incremented by the mass of the asteroid it just destroyed, enabling us to potentially destroy larger asteroids in the subsequent iterations.
After the for loop concludes (if we haven't returned False for any asteroid), it means the planet was able to destroy all asteroids in ascending order of their mass and thus able to survive. Hence, the function returns True.
The overall time complexity of the solution is governed by the sorting process, which, in Python, performs at O(n log n) complexity, with n being the number of asteroids.

This problem doesn't require any additional data structures; a list to hold the input array and a single variable to track the planet's mass are sufficient. The pattern used here is a common one in algorithm design: make the locally optimal choice at each iteration with the hope of finding the global optimum — a hallmark of greedy algorithms.

Here is the relevant portion of the solution code for reference:

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

Each element of the asteroids list is examined exactly once after the list has been sorted, and this approach guarantees that the planet will destroy the asteroids in the most optimal sequence.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's use a small example to illustrate the solution approach.

Imagine a planet with a mass of 10, and a sequence of asteroids with the following masses: [3, 9, 19, 5, 12]. We want to determine if the planet can survive the impact of all these asteroids one by one, absorbing any that it can destroy.

First, we employ a greedy strategy and sort the asteroids by mass in ascending order: Sorted asteroids: [3, 5, 9, 12, 19].

Now, let's walk through the sorted list and simulate the planet's collisions with the asteroids:

The first asteroid has a mass of 3, which is less than the planet's mass of 10. The planet can destroy it and absorb its mass.
- New planet mass: 10 + 3 = 13.
The next asteroid has a mass of 5, which is less than the planet's new mass of 13. The planet can destroy it as well.
- New planet mass: 13 + 5 = 18.
The third asteroid's mass is 9, and again, it is less than the planet's current mass of 18. The planet destroys and absorbs this asteroid too.
- New planet mass: 18 + 9 = 27.
The fourth asteroid has a mass of 12, which is also less than the planet's mass of 27. The planet continues to absorb the asteroid's mass.
- New planet mass: 27 + 12 = 39.
Finally, the last asteroid has a mass of 19. As the planet's mass is now 39, it can easily destroy and absorb this asteroid.
- New planet mass: 39 + 19 = 58.

Since the planet has successfully absorbed each asteroid in turn, growing more massive each time, it can survive all collisions in this specific sequence. Therefore, the function will return True - the planet survives.

Here’s how the code will execute this example:

class Solution:
    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:
        asteroids.sort()  # [3, 5, 9, 12, 19]
        for v in asteroids:
            if mass < v:  # This check will fail for all asteroids in this example
                return False
            mass += v  # Planet's mass incrementally grows: 13, 18, 27, 39, 58
        return True  # The planet survived all asteroids.

# Test the example
solution = Solution()
assert solution.asteroidsDestroyed(10, [3, 9, 19, 5, 12]) == True

This example demonstrated the greedy strategy in action. By sorting the asteroids by mass and absorbing them starting with the smallest mass, the planet was able to successfully destroy and absorb all incoming asteroids.

Solution Implementation

1from typing import List
2
3class Solution:
4    def asteroidsDestroyed(self, current_mass: int, asteroids: List[int]) -> bool:
5        # Sort the list of asteroids in ascending order based on their mass.
6        asteroids.sort()
7      
8        # Iterate through the sorted list of asteroids.
9        for asteroid_mass in asteroids:
10            # If the current mass is less than the next asteroid's mass,
11            # the asteroid cannot be destroyed, hence return False.
12            if current_mass < asteroid_mass:
13                return False
14          
15            # Add the mass of the destroyed asteroid to the current mass.
16            current_mass += asteroid_mass
17      
18        # If all asteroids have been successfully destroyed, return True.
19        return True
20
21# Example usage:
22# solution = Solution()
23# result = solution.asteroidsDestroyed(10, [3, 9, 19, 5, 21])
24# print(result)  # This would print False, as the 19 and 21 cannot be destroyed.
25

1import java.util.Arrays; // Import Arrays class for sorting.
2
3class Solution {
4    // Method to determine if all asteroids can be destroyed.
5    public boolean asteroidsDestroyed(int mass, int[] asteroids) {
6        // Sort the asteroids array to process them in ascending order.
7        Arrays.sort(asteroids);
8
9        // Use long to avoid integer overflow as mass might become larger than int range.
10        long currentMass = mass;
11      
12        // Iterate through the sorted asteroids.
13        for (int asteroidMass : asteroids) {
14            // If the current asteroid mass is larger than the current mass, destruction is not possible.
15            if (currentMass < asteroidMass) {
16                return false;
17            }
18            // Otherwise, add the asteroid's mass to the current mass.
19            currentMass += asteroidMass;
20        }
21      
22        // Return true if all asteroids have been successfully destroyed.
23        return true;
24    }
25}
26

1#include <vector>
2#include <algorithm> // For std::sort
3
4class Solution {
5public:
6    // Function checks if all asteroids can be destroyed given the initial mass
7    bool asteroidsDestroyed(int initialMass, vector<int>& asteroids) {
8        // Sort the asteroids in non-decreasing order to handle smaller asteroids first
9        std::sort(asteroids.begin(), asteroids.end());
10      
11        // Use a long long type for currentMass to avoid overflow issues
12        long long currentMass = initialMass;
13      
14        // Loop through the sorted asteroids
15        for (int asteroidMass : asteroids) {
16            // If the current asteroid is heavier than the current mass, return false
17            if (currentMass < asteroidMass) {
18                return false;
19            }
20            // Otherwise, add the mass of the destroyed asteroid to the current mass
21            currentMass += asteroidMass;
22        }
23      
24        // If all asteroids have been successfully destroyed, return true
25        return true;
26    }
27};
28

1// Include typing for the asteroid array
2type AsteroidArray = number[];
3
4// Define a global variable for initial mass (assuming we want to track it globally)
5let initialMass: number = 0;
6
7// Function checks if all asteroids can be destroyed given the initial mass
8function asteroidsDestroyed(mass: number, asteroids: AsteroidArray): boolean {
9    // Sort the asteroids in non-decreasing order to handle smaller asteroids first
10    asteroids.sort((a, b) => a - b);
11
12    // Use a bigint type for currentMass to avoid overflow issues
13    let currentMass: bigint = BigInt(mass);
14
15    // Loop through the sorted asteroids
16    for (let asteroidMass of asteroids) {
17        let massBigInt = BigInt(asteroidMass);
18      
19        // If the current asteroid is heavier than the current mass, return false
20        if (currentMass < massBigInt) {
21            return false;
22        }
23      
24        // Otherwise, add the mass of the destroyed asteroid to the current mass
25        currentMass += massBigInt;
26    }
27
28    // If all asteroids have been successfully destroyed, return true
29    return true;
30}
31

Time and Space Complexity

The time complexity of the code is O(n log n) where n is the number of asteroids. This is because the most time-consuming operation is the sort function, which typically has O(n log n) complexity.

The space complexity of the code is O(1) assuming that the sort is done in-place (as is typical with Python's sort on lists). This means that aside from a constant amount of additional space, the code does not require extra space that scales with the input size.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

How does merge sort divide the problem into subproblems?

Divide the array into two equal halves by index

Divide the array into two based on whether an element is smaller than an arbitrary value

Divide the array into a stray element and the rest of the array

Merge sort does not use divide and conquer

I don’t know