Asteroids Destroyed
Problem
Given an initial mass and a list of asteroid masses, determine if all asteroids can be destroyed sequentially by absorbing smaller or equal mass asteroids, increasing the mass accordingly.
- 1 ≤ mass ≤ 10⁵
- 1 ≤ asteroids.length ≤ 10⁵
- 1 ≤ asteroids[i] ≤ 10⁵
Example
mass = 10, asteroids = [3,9,19,5,21]trueSorting the asteroids yields [3,5,9,19,21]. The planet starts with mass 10. It destroys asteroid 3 (mass 3), increasing mass to 13. Then destroys 5, mass becomes 18. Then 9, mass becomes 27. Then 19, mass becomes 46. Finally, 21, mass becomes 67. At each step, the planet's mass is sufficient to destroy the next asteroid, so the output is true.
Approach
Straightforward Solution
A brute-force approach would try all permutations of asteroid destruction orders, which is factorial in time complexity and infeasible for large inputs.
Core Observation
The planet must destroy asteroids in an order that ensures it can absorb each one. Since absorbing smaller asteroids first increases the planet's mass, sorting the asteroids in ascending order guarantees the planet always faces the smallest available asteroid next, maximizing the chance to absorb all.
Path to Optimal
The key insight is that the order of destruction matters and that destroying smaller asteroids first is always beneficial. Sorting the asteroids allows a greedy approach where the planet attempts to destroy asteroids from smallest to largest. If at any point the planet's mass is less than the current asteroid's mass, it cannot proceed, and the answer is false.
Optimal Approach
Sort the asteroids array in ascending order. Iterate through the sorted list, and for each asteroid, check if the planet's current mass is at least the asteroid's mass. If not, return false immediately. Otherwise, add the asteroid's mass to the planet's mass and continue. If all asteroids are destroyed, return true.
Time
O(n log n)
Sorting the asteroids takes O(n log n) time. The subsequent single pass through the sorted list is O(n), so the overall time complexity is dominated by sorting.
Space
O(1)
The algorithm sorts the input array in place and uses only a constant amount of extra space for variables tracking mass and iteration.
Pattern Spotlight
Greedy Algorithms (Incremental Accumulation)
When a problem involves sequentially consuming or absorbing elements to maximize capacity or resources, sorting and processing from smallest to largest often ensures feasibility by incrementally building capacity before facing larger challenges.
Solution
| 1 | class Solution:
|
| 2 | def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:
|
| 3 | asteroids.sort()
|
| 4 | for asteroid in asteroids:
|
| 5 | if asteroid > mass:
|
| 6 | return False
|
| 7 | mass += asteroid
|
| 8 |
|
| 9 | return True |
Step-by-Step Solution
Sort Asteroids to Enable Greedy Sequential Absorption
| 3 | asteroids.sort()
|
Objective
To arrange asteroids in ascending order so the planet can absorb them starting from the smallest mass.
Key Insight
Sorting ensures the planet always faces the smallest asteroid next, maximizing the chance to absorb it and increase mass before tackling larger asteroids. This ordering transforms a complex permutation problem into a simple linear scan.
Interview Quick-Check
Core Logic
Sorting the asteroids array is the foundational step that enables the greedy absorption strategy.
Common Pitfalls & Bugs
Failing to sort can lead to incorrect results because the planet might encounter a large asteroid before gaining enough mass.
Iterate Through Sorted Asteroids and Absorb Sequentially
| 4 | for asteroid in asteroids:
|
| 5 | if asteroid > mass:
|
| 6 | return False
|
| 7 | mass += asteroid
|
Objective
To check if the planet can absorb each asteroid in ascending order and update its mass accordingly.
Key Insight
At each step, the planet must have enough mass to destroy the current asteroid. If it does, absorbing the asteroid increases the planet's mass, enabling it to handle larger asteroids later. If not, the process fails immediately, avoiding unnecessary computation.
Interview Quick-Check
Core Logic
The loop checks the feasibility of destroying each asteroid in order and updates the planet's mass to reflect absorption.
State & Boundaries
The iteration stops early and returns false if the planet's mass is insufficient for any asteroid.
Common Pitfalls & Bugs
Not returning false immediately upon failure leads to incorrect results or wasted computation.
Return True if All Asteroids Are Successfully Destroyed
| 9 | return True |
Objective
To confirm that the planet has absorbed all asteroids and return the success result.
Key Insight
If the loop completes without returning false, it means the planet's mass was sufficient at every step, so the answer is true.
Interview Quick-Check
Core Logic
Returning true after the loop confirms all asteroids were destroyed in the greedy sequence.
Line Analysis
This solution has 3 Critical lines interviewers watch for.
if asteroid > mass:Check if the current asteroid's mass exceeds the planet's mass.
This condition detects the critical failure point where the planet cannot absorb the asteroid, enabling early termination.
asteroids.sort()Sort the asteroids array in ascending order.
Sorting arranges asteroids so the planet can absorb smaller ones first, incrementally increasing its mass to handle larger asteroids later.
return FalseReturn false immediately if the asteroid cannot be absorbed.
Early return prevents unnecessary computation and correctly signals that the destruction sequence is impossible.
mass += asteroidIncrease the planet's mass by the absorbed asteroid's mass.
Absorbing an asteroid increases the planet's mass, enabling it to absorb larger asteroids subsequently, which is the core of the greedy accumulation strategy.
for asteroid in asteroids:Begin iterating through each asteroid in sorted order.
Sequential iteration allows checking the planet's ability to absorb each asteroid in turn, ensuring correctness of the greedy approach.
return TrueReturn true after successfully absorbing all asteroids.
Completing the loop without failure means the planet destroyed all asteroids, so returning true correctly reports success.
Test Your Understanding
Why does sorting the asteroids in ascending order guarantee the optimal destruction sequence?
Because destroying smaller asteroids first increases the planet's mass early, enabling it to absorb larger asteroids later. Any other order risks encountering a large asteroid too soon, making destruction impossible.
Related Problems
Greedy pattern
Don't just read it. Drill it.
Reconstruct Asteroids Destroyed from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Asteroids Destroyed drill