2126. Destroying Asteroids

Array
Greedy
Counting Sort

TIME

O(n + M)

SPACE

O(M)

Intuition

Destroying an asteroid only increases the planet's mass. Therefore, it is always safe to destroy the smallest remaining asteroid first.

If the planet cannot destroy the smallest remaining asteroid, then it cannot destroy any larger remaining asteroid either. No valid order exists in that case.

The asteroid masses are bounded by 10^5, so we do not need comparison sorting. Instead, count how many asteroids have each mass and process possible masses in ascending order.

Approach

Create a frequency array where frequency[value] is the number of asteroids with that mass.
Iterate possible asteroid masses in ascending order.
For each mass with at least one asteroid:
- if the planet's current mass is smaller, return false
- otherwise, destroy all asteroids of this mass and add mass * frequency[mass] to the planet
Return true after all masses are processed.

Complexity

Let M be the maximum asteroid mass. Here, M <= 10^5.

Time: O(n + M), build the frequency array, then scan possible masses
Space: O(M), for the frequency array

Edge Cases

Planet mass exactly equals an asteroid's mass -> collision succeeds
The smallest asteroid is too large -> return false immediately
Multiple asteroids have the same mass -> absorb them as one batch
One asteroid -> compare it directly with the planet's mass
Large accumulated mass -> use a wide integer type in Java

Code

from typing import List


class Solution:
    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:
        """
        2126. Destroying Asteroids
        Time: O(n + M)
        Space: O(M)
        """
        max_asteroid = max(asteroids)
        frequency = [0] * (max_asteroid + 1)

        for asteroid in asteroids:
            frequency[asteroid] += 1

        for asteroid_mass, count in enumerate(frequency):
            if count == 0:
                continue

            if mass < asteroid_mass:
                return False
            mass += asteroid_mass * count

        return True

/**
 * 2126. Destroying Asteroids
 * Time: O(n + M)
 * Space: O(M)
 */
class Solution {
    public boolean asteroidsDestroyed(int mass, int[] asteroids) {
        int maxAsteroid = 0;
        for (int asteroid : asteroids) {
            maxAsteroid = Math.max(maxAsteroid, asteroid);
        }

        int[] frequency = new int[maxAsteroid + 1];
        for (int asteroid : asteroids) {
            frequency[asteroid]++;
        }

        long currentMass = mass;

        for (int asteroidMass = 1; asteroidMass <= maxAsteroid; asteroidMass++) {
            if (frequency[asteroidMass] == 0) {
                continue;
            }

            if (currentMass < asteroidMass) {
                return false;
            }
            currentMass += (long) asteroidMass * frequency[asteroidMass];
        }

        return true;
    }
}