Leetcode 2126: Destroying Asteroids

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.