Destroying Asteroids

medium array greedy sorting

Problem

A planet starts with a given mass and faces a list of asteroids, each with its own mass. The planet meets the asteroids one at a time, in any order you choose. When it meets an asteroid whose mass is less than or equal to the planet's current mass, the planet destroys it and gains that asteroid's mass; otherwise the planet itself is destroyed. Return true if there is an order in which the planet can destroy every asteroid, and false otherwise.

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

Outputtrue

Hit them smallest-first: 10→13→18→27→46→67. Every asteroid is no heavier than the planet at the moment of impact, so all are destroyed.

asteroids (comma-separated)

mass

def asteroids_destroyed(mass, asteroids):
    asteroids.sort()
    total = mass
    for a in asteroids:
        if a > total:
            return False
        total += a
    return True

function asteroidsDestroyed(mass, asteroids) {
  asteroids.sort((a, b) => a - b);
  let total = mass;
  for (const a of asteroids) {
    if (a > total) return false;
    total += a;
  }
  return true;
}

class Solution {
    public boolean asteroidsDestroyed(int mass, int[] asteroids) {
        Arrays.sort(asteroids);
        long total = mass;
        for (int a : asteroids) {
            if (a > total) return false;
            total += a;
        }
        return true;
    }
}

bool asteroidsDestroyed(int mass, vector<int>& asteroids) {
    sort(asteroids.begin(), asteroids.end());
    long long total = mass;
    for (int a : asteroids) {
        if (a > total) return false;
        total += a;
    }
    return true;
}

Explanation

The planet only ever grows — every asteroid it destroys is added to its mass. So the planet is at its weakest at the very start and gets stronger with each kill. The question is whether an order exists that never asks the planet to face an asteroid it can't handle.

The greedy insight: always take the smallest remaining asteroid first. If the planet can't destroy the smallest one available, it certainly can't destroy any of the larger ones either — and since destroying that small asteroid only makes the planet bigger, there's never a reason to save it for later. Taking the lightest one first is always at least as good as any other choice.

So we sort the asteroids in ascending order and walk through them, keeping a running total that starts at the planet's mass. For each asteroid a, if a > total the planet is destroyed and we return false. Otherwise the planet absorbs it: total += a.

If we make it through the whole sorted list, an order exists that destroys everything, so we return true.

Example: mass = 10, asteroids = [3, 9, 19, 5, 21] sorts to [3, 5, 9, 19, 21]. Running mass: 10 → 13 → 18 → 27 → 46 → 67. No asteroid ever exceeds the current mass, so the answer is true.

One detail worth noting: the mass can grow large, so languages with fixed-size integers (Java, C++) should accumulate the total in a 64-bit type to avoid overflow.

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