Leetcode 2126: Destroying Asteroids

Pierre-Marie Poitevin
3 min readJan 3, 2022

In this Leetcode problem we are trying to save the planet! We should determine if the planet can survive a series of asteroids. We can pick the order in which asteroids hit. This is the problem statement:

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 if all asteroids can be destroyed. Otherwise, return false.

We are also given some examples:

Examples

The one observation that helps with solving the problem is that, if we can pick the order, we should tackle asteroid from smallest to largest. The reason for this is that once we tackle an asteroid A, the planet will have the mass mass + sum(mass of smaller asteroids). We can show that if the asteroid has a mass larger than mass + sum(mass of smaller asteroids), then the planet will be destroyed. Therefore, sorting the asteroids by mass is the optimal choice here.

Jamboard of example and optimal sorting

Then to solve the problem we will:

  1. Sort the asteroids array
  2. For each asteroid, if it isn’t larger than the current planet, add its mass to the current mass. Else return false.

This is the code in C:

int cmpfunc (const void * a, const void * b) {
return ( *(int*)a - *(int*)b );
}
bool asteroidsDestroyed(
int mass,
int* asteroids,
int asteroidsSize){
qsort(asteroids, asteroidsSize, sizeof(int), cmpfunc);
long currentMass = mass;
for (int i = 0; i < asteroidsSize; i++) {
int x = asteroids[i];
if (x > currentMass) {
return false;
}
currentMass += x;
}
return true;
}

--

--