How do you solve Destroying Asteroids on LeetCode?

Destroying Asteroids (LeetCode #2126) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n log n) time complexity and O(1) space complexity. Key insight: Sorting the asteroids allows for a greedy approach to maximize mass gain.

What is the time complexity of Destroying Asteroids?

The optimal solution for Destroying Asteroids runs in O(n log n) time and uses O(1) space. The time complexity is O(n log n) due to sorting the asteroids, and O(1) for space as we are modifying the input array in place.

What is the brute force solution for Destroying Asteroids?

The brute force approach for Destroying Asteroids is Brute Force, with O(n²) time complexity and O(n) space complexity. We can try every possible order of colliding with asteroids and check if the planet survives. This approach is straightforward but inefficient as it explores all permutations. The optimal Optimal Solution approach improves this to O(n log n).

What algorithm or data structure is used to solve Destroying Asteroids?

Destroying Asteroids uses the following concepts: Array, Greedy, Sorting. The recommended patterns to study are: Greedy, Sorting, Array.

What are the interview tips for Destroying Asteroids?

Always consider edge cases, such as the smallest and largest asteroids. Explain your thought process clearly, especially when transitioning from brute force to optimal solutions. Practice coding the optimal solution without looking at references to build confidence.

What are common mistakes when solving Destroying Asteroids?

Not considering the order of collisions, which can lead to incorrect results. Overlooking the need to sort the asteroids for the optimal approach.

#2126

Destroying Asteroids

Medium

ArrayGreedySortingGreedySortingArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n log n)
Space	O(n)	O(1)

💡

Intuition

Time O(n log n)Space O(1)

By sorting the asteroids and colliding with the smallest first, we ensure that we maximize the planet's mass gain at each step, which is a greedy approach.

⚙️

Algorithm

5 steps

1Step 1: Sort the asteroids array in ascending order.
2Step 2: Initialize current_mass with the planet's mass.
3Step 3: Iterate through the sorted asteroids and check if current_mass is greater than or equal to the asteroid's mass.
4Step 4: If yes, add the asteroid's mass to current_mass. If no, return false.
5Step 5: If all asteroids are processed, return true.

solution.py11 lines

1# Full working Python code
2
3def canDestroyAsteroids(mass, asteroids):
4    asteroids.sort()
5    current_mass = mass
6    for asteroid in asteroids:
7        if current_mass >= asteroid:
8            current_mass += asteroid
9        else:
10            return False
11    return True

ℹ

Complexity note: The time complexity is O(n log n) due to sorting the asteroids, and O(1) for space as we are modifying the input array in place.

1Sorting the asteroids allows for a greedy approach to maximize mass gain.
2If the planet cannot destroy an asteroid, it cannot destroy any larger asteroid.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.