2126. Destroying Asteroids

Time: O(n log n)

Space: O(log n)

Intuition

Larger asteroids block smaller ones only if they come before them. So if we sort asteroids by size and absorb them left-to-right, each successful absorption increases our mass for later asteroids. A greedy strategy of always absorbing in order works because the sorted order is optimal.

Algorithm

1Sort the asteroids array in ascending order.
2Start with the given initial mass.
3For each asteroid in sorted order:
4 If current mass >= asteroid size, absorb it by adding to mass.
5 Otherwise, return false (planet destroyed).
6If all asteroids are absorbed, return true.

Example Walkthrough

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

1.Sorted: [3, 5, 9, 19, 21].
2.Absorb 3: mass = 13.
3.Absorb 5: mass = 18.
4.Absorb 9: mass = 27, now strong enough for 19 and 21.

Output: true

Common Pitfalls

•Without sorting, you cannot determine order of collisions in the array; sorting gives a valid sequence.
•Greedy absorption is safe because sorted order ensures future asteroids are at least as large.
•Use long for mass accumulation to avoid integer overflow.

2126.cs

// Approach: Greedy with sorting. Sort asteroids by size, then absorb them left-to-right as long as mass allows.
// Each absorbed asteroid adds its mass, increasing capacity for larger ones. If any asteroid is too large, return false.
// Time: O(n log n) Space: O(log n) for sorting

public class Solution
{
    public bool AsteroidsDestroyed(int mass, int[] asteroids)
    {
        Array.Sort(asteroids);

        long m = mass;

        foreach (int asteroid in asteroids)
        {
            if (m >= asteroid)
                m += asteroid;
            else
                return false;
        }

        return true;
    }
}

Was this solution helpful?