LeetCode 2126 - Destroying Asteroids

LeetCode Problem 2126

Difficulty: 🟡 Medium
Topics: Array, Greedy, Sorting

Solution

Problem Understanding

In this problem, we are given the starting mass of a planet and a list of asteroid masses. The planet can collide with the asteroids in any order we choose. Every time the planet collides with an asteroid, one of two things happens:

• If the planet's current mass is greater than or equal to the asteroid's mass, the asteroid is destroyed, and the planet gains that asteroid's mass.
• Otherwise, the planet is destroyed immediately, and the process fails.

The goal is to determine whether there exists some ordering of the asteroids such that the planet can destroy all of them successfully.

The important detail is that we are allowed to reorder the asteroids arbitrarily. This transforms the problem from a fixed simulation problem into an optimization problem where we must choose the best sequence of collisions.

The input consists of:

• mass, the initial mass of the planet.
• asteroids, an array where each value represents the mass of one asteroid.

The output is a boolean:

• true if all asteroids can be destroyed.
• false otherwise.

The constraints are large enough that efficiency matters:

• Up to 10^5 asteroids
• Each asteroid mass can also be up to 10^5

A quadratic solution would be too slow, so we need something around O(n log n) or better.

Several edge cases are important:

• A single asteroid larger than the initial mass.
• Many tiny asteroids that gradually increase the planet's mass.
• Duplicate asteroid masses.
• Already sorted or reverse sorted inputs.
• Cases where destroying almost every asteroid still leaves the planet too small for the final one.

Because the planet's mass continuously increases after successful collisions, the order of processing matters significantly.

Approaches

Brute Force Approach

The brute force idea is to try every possible ordering of the asteroids and simulate the collisions.

For each permutation:

1. Start with the initial planet mass.
2. Process asteroids in that order.
3. If the planet can destroy every asteroid, return true.
4. Otherwise, try another permutation.

This approach is correct because it explicitly checks all possible valid orders. If any successful order exists, brute force will eventually find it.

However, this approach is completely impractical for the given constraints. If there are n asteroids, there are n! possible orderings. Even for relatively small values of n, factorial growth becomes enormous.

For example:

• 10! = 3,628,800
• 15! is already astronomically large

Since n can be 100,000, brute force is impossible.

Optimal Greedy Approach

The key observation is that the best strategy is always to destroy the smallest asteroid currently available.

Why does this work?

If the planet can destroy a small asteroid, it gains additional mass with minimal risk. Destroying smaller asteroids first maximizes the planet's growth before attempting larger asteroids.

Suppose we have two asteroids:

• Small asteroid: a
• Large asteroid: b
• where a <= b

If the planet cannot destroy a, it definitely cannot destroy b.

If the planet can destroy b, it can also destroy a, and destroying a first only increases the planet's mass, making b easier afterward.

This means sorting the asteroids in ascending order is always optimal.

The algorithm becomes:

1. Sort the asteroids.
2. Iterate from smallest to largest.
3. If the current asteroid is too large, return false.
4. Otherwise, absorb it and continue.

This greedy strategy guarantees correctness.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n! × n)	O(n)	Tries every possible ordering
Optimal	O(n log n)	O(1) or O(log n) depending on sorting	Sort ascending and greedily absorb asteroids

Algorithm Walkthrough

Step 1: Sort the asteroids

Sort the asteroids array in ascending order.

The reason for sorting is that smaller asteroids are always safer to destroy first. Every successful collision increases the planet's mass, which improves our chances against larger asteroids later.

For example:

asteroids = [3, 9, 19, 5, 21]

After sorting:

[3, 5, 9, 19, 21]

Step 2: Track the current planet mass

Initialize a variable to store the current planet mass.

Initially:

current_mass = mass

This value changes after every successful collision.

Step 3: Process asteroids from smallest to largest

Iterate through the sorted array.

For each asteroid:

• If current_mass < asteroid, the planet cannot destroy it, so return false.
• Otherwise, add the asteroid mass to current_mass.

This greedily maximizes future growth.

Step 4: Finish successfully

If the loop completes without failure, every asteroid was destroyed successfully.

Return true.

Why it works

The greedy strategy works because destroying smaller asteroids first can never hurt us.

If an asteroid cannot be destroyed now, then any larger asteroid also cannot be destroyed now. Conversely, if a smaller asteroid can be destroyed, absorbing it only increases the planet's mass and improves future possibilities.

Therefore, processing asteroids in ascending order always gives the maximum possible growth at every step. If this strategy fails, no alternative ordering could succeed.

Python Solution

from typing import List

class Solution:
    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:
        asteroids.sort()

        current_mass = mass

        for asteroid in asteroids:
            if current_mass < asteroid:
                return False

            current_mass += asteroid

        return True

The implementation begins by sorting the asteroid array in ascending order. This directly applies the greedy insight that smaller asteroids should always be handled first.

The variable current_mass stores the evolving mass of the planet. We initialize it with the given starting mass.

The loop iterates through every asteroid in sorted order. For each asteroid, we first check whether the planet is large enough to destroy it. If not, we immediately return False because no future ordering could succeed once the smallest remaining asteroid is already too large.

If the collision succeeds, the asteroid's mass is added to current_mass, simulating the absorption process.

If the loop finishes completely, then all asteroids were destroyed successfully, so the method returns True.

Go Solution

package main

import "sort"

func asteroidsDestroyed(mass int, asteroids []int) bool {
	sort.Ints(asteroids)

	currentMass := int64(mass)

	for _, asteroid := range asteroids {
		if currentMass < int64(asteroid) {
			return false
		}

		currentMass += int64(asteroid)
	}

	return true
}

The Go implementation follows the same logic as the Python solution.

One important difference is the use of int64 for currentMass. While the constraints individually fit within standard integers, repeated additions can grow significantly larger than the initial values. Using int64 avoids overflow concerns during accumulation.

The built in sort.Ints() function efficiently sorts the slice in ascending order.

Go slices are naturally dynamic views over arrays, so no extra copying is needed for iteration.

Worked Examples

Example 1

Input:

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

After sorting:

[3,5,9,19,21]

Step	Current Mass	Asteroid	Can Destroy?	New Mass
1	10	3	Yes	13
2	13	5	Yes	18
3	18	9	Yes	27
4	27	19	Yes	46
5	46	21	Yes	67

All asteroids are destroyed successfully.

Result:

true

Example 2

Input:

mass = 5
asteroids = [4,9,23,4]

After sorting:

[4,4,9,23]

Step	Current Mass	Asteroid	Can Destroy?	New Mass
1	5	4	Yes	9
2	9	4	Yes	13
3	13	9	Yes	22
4	22	23	No	Failure

The final asteroid is too large.

Result:

false

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates the runtime
Space	O(1) or O(log n)	Depends on the sorting implementation

The main cost comes from sorting the asteroid array. After sorting, the algorithm performs a single linear scan through the array.

The iteration itself is O(n), but sorting requires O(n log n), which dominates the total runtime.

The additional memory usage is minimal because the algorithm only stores a few variables besides the input array. The exact auxiliary space depends on the language's sorting implementation.

Test Cases

from typing import List

class Solution:
    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:
        asteroids.sort()

        current_mass = mass

        for asteroid in asteroids:
            if current_mass < asteroid:
                return False

            current_mass += asteroid

        return True

solution = Solution()

assert solution.asteroidsDestroyed(10, [3, 9, 19, 5, 21]) is True
# Provided example where all asteroids can be destroyed

assert solution.asteroidsDestroyed(5, [4, 9, 23, 4]) is False
# Provided example where final asteroid is too large

assert solution.asteroidsDestroyed(1, [1]) is True
# Smallest possible valid input

assert solution.asteroidsDestroyed(1, [2]) is False
# Single asteroid larger than initial mass

assert solution.asteroidsDestroyed(100, [1, 2, 3, 4]) is True
# Initial mass already exceeds every asteroid

assert solution.asteroidsDestroyed(3, [1, 2, 3]) is True
# Exact equality should still succeed

assert solution.asteroidsDestroyed(3, [4]) is False
# Immediate failure case

assert solution.asteroidsDestroyed(8, [1, 1, 1, 20]) is False
# Many small gains still insufficient

assert solution.asteroidsDestroyed(8, [1, 1, 1, 10]) is True
# Gradual accumulation eventually succeeds

assert solution.asteroidsDestroyed(10, [10, 10, 10]) is True
# Repeated equal values

assert solution.asteroidsDestroyed(2, [1, 3, 2]) is True
# Sorting is necessary for success

assert solution.asteroidsDestroyed(100000, [100000] * 100000) is True
# Large stress test with maximum values

Test	Why
mass=10, [3,9,19,5,21]	Validates the standard successful scenario
mass=5, [4,9,23,4]	Validates failure after partial progress
mass=1, [1]	Smallest successful input
mass=1, [2]	Smallest failing input
mass=100, [1,2,3,4]	Planet starts overwhelmingly large
mass=3, [1,2,3]	Confirms equality is allowed
mass=3, [4]	Immediate impossible collision
mass=8, [1,1,1,20]	Gradual growth still insufficient
mass=8, [1,1,1,10]	Growth eventually enables success
mass=10, [10,10,10]	Handles duplicates and equal masses
mass=2, [1,3,2]	Demonstrates why sorting matters
Large maximum-value test	Stress tests performance and accumulation

Edge Cases

One important edge case occurs when the planet's mass is exactly equal to an asteroid's mass. The problem statement says the planet succeeds when its mass is greater than or equal to the asteroid. A common bug is accidentally using a strict greater-than comparison. This implementation correctly uses < for failure detection, so equality succeeds properly.

Another important case is when the smallest asteroid is already too large. Since the array is sorted, if the first asteroid cannot be destroyed, no other ordering could possibly work. The implementation immediately returns False in this situation without unnecessary computation.

A third important edge case involves very large cumulative mass growth. Even though individual asteroid values are only up to 10^5, repeatedly adding them can create very large totals. In Go specifically, using standard int carelessly could risk overflow on some systems. The Go implementation avoids this by using int64 for the running mass total.

Another subtle edge case is when success depends entirely on choosing the correct order. For example:

mass = 2
asteroids = [1,3,2]

If processed in the given order:

2 -> destroy 1 -> mass 3
3 -> destroy 3 -> mass 6
6 -> destroy 2

Success occurs.

But an unfavorable order such as [3,1,2] would fail immediately. Sorting guarantees we always choose the safest growth strategy first.