How do you solve Asteroids Destroyed?

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.

Asteroids Destroyed

Q: What is the time complexity of Asteroids Destroyed?

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.

Q: What pattern does Asteroids Destroyed use?

The Pattern: Greedy Algorithms (Incremental Accumulation) The Heuristic: 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.

Medium Greedy Algorithms

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

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

Output: true

Sorting 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

Preview

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…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

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…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

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

Python

1class Solution:
  def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:
      asteroids.sort()
      for asteroid in asteroids:
          if asteroid > mass:
              return False
          mass += asteroid
      
      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

To check if the planet can absorb each asteroid in ascending order and update its mass accordingly.

Return True if All Asteroids Are Successfully Destroyed

To confirm that the planet has absorbed all asteroids and return the success result.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 3 Critical lines interviewers watch for.

Line 5 Critical

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.

Line 3 Critical

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.

Line 6 Critical

return False

Return false immediately if the asteroid cannot be absorbed.

Early return prevents unnecessary computation and correctly signals that the destruction sequence is impossible.

Full line-by-line criticality + rationale for all 6 lines available on Pro.

Test Your Understanding

Why does sorting the asteroids in ascending order guarantee the optimal destruction sequence?

See the answer with Pro.

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

or drill a free problem

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`