Problem

You are given an integer mass, which represents the original mass of a planet. You are further given an integer array asteroids, where asteroids[i] is the mass of the ith asteroid.

You can arrange for the planet to collide with the asteroids in any arbitrary order. If the mass of the planet is greater than or equal to the mass of the asteroid, the asteroid is destroyed and the planet gains the mass of the asteroid. Otherwise, the planet is destroyed.

Return true _ifall asteroids can be destroyed. Otherwise, return _false .

Examples

Example 1

1
2
3
4
5
6
7
8
9

Input: mass = 10, asteroids = [3,9,19,5,21]
Output: true
Explanation: One way to order the asteroids is [9,19,5,3,21]:
- The planet collides with the asteroid with a mass of 9. New planet mass: 10 + 9 = 19
- The planet collides with the asteroid with a mass of 19. New planet mass: 19 + 19 = 38
- The planet collides with the asteroid with a mass of 5. New planet mass: 38 + 5 = 43
- The planet collides with the asteroid with a mass of 3. New planet mass: 43 + 3 = 46
- The planet collides with the asteroid with a mass of 21. New planet mass: 46 + 21 = 67
All asteroids are destroyed.

Example 2

1
2
3
4
5
6

Input: mass = 5, asteroids = [4,9,23,4]
Output: false
Explanation: 
The planet cannot ever gain enough mass to destroy the asteroid with a mass of 23.
After the planet destroys the other asteroids, it will have a mass of 5 + 4 + 9 + 4 = 22.
This is less than 23, so a collision would not destroy the last asteroid.

Constraints

  • 1 <= mass <= 10^5
  • 1 <= asteroids.length <= 10^5
  • 1 <= asteroids[i] <= 10^5

Solution

Method 1 – Greedy (Sort and Simulate)

Intuition

Always destroy the smallest asteroid you can, so sort the asteroids and try to absorb them in order. If at any point the planet’s mass is less than the asteroid, you lose.

Approach

  1. Sort the asteroids array.
  2. For each asteroid, if mass >= asteroid, add asteroid to mass. Else, return false.
  3. If all asteroids are destroyed, return true.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

import "sort"
func asteroidsDestroyed(mass int, asteroids []int) bool {
    sort.Ints(asteroids)
    m := int64(mass)
    for _, a := range asteroids {
        if m < int64(a) {
            return false
        }
        m += int64(a)
    }
    return true
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

import java.util.Arrays;
class Solution {
    public boolean asteroidsDestroyed(int mass, int[] asteroids) {
        Arrays.sort(asteroids);
        long m = mass;
        for (int a : asteroids) {
            if (m < a) return false;
            m += a;
        }
        return true;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    fun asteroidsDestroyed(mass: Int, asteroids: IntArray): Boolean {
        asteroids.sort()
        var m = mass.toLong()
        for (a in asteroids) {
            if (m < a) return false
            m += a
        }
        return true
    }
}
1
2
3
4
5
6
7
8
9

class Solution:
    def asteroidsDestroyed(self, mass: int, asteroids: list[int]) -> bool:
        asteroids.sort()
        m = mass
        for a in asteroids:
            if m < a:
                return False
            m += a
        return True
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

impl Solution {
    pub fn asteroids_destroyed(mass: i64, mut asteroids: Vec<i32>) -> bool {
        asteroids.sort();
        let mut m = mass;
        for &a in &asteroids {
            if m < a as i64 {
                return false;
            }
            m += a as i64;
        }
        true
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    asteroidsDestroyed(mass: number, asteroids: number[]): boolean {
        asteroids.sort((a, b) => a - b);
        let m = BigInt(mass);
        for (const a of asteroids) {
            if (m < BigInt(a)) return false;
            m += BigInt(a);
        }
        return true;
    }
}

Complexity

  • ⏰ Time complexity: O(n log n), for sorting the asteroids array.
  • 🧺 Space complexity: O(1), ignoring the input array and sort’s stack usage.