Show problems as
Classic problem #2126MediumArrayGreedySorting

Destroying Asteroids

Real-world version: Snowball Down the Slope
Tracked in this browser only
Read Destroying Asteroids on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A snowball of weight mass is set rolling past a line of clumps whose weights are given as asteroids. The clumps may be taken in any order you like.

The snowball takes a clump only when its own weight is at least that clump's weight, and taking it adds the clump's weight to the snowball. Meeting a clump heavier than the snowball ends the run.

Return true when some order lets the snowball take every clump.

Examples

Example 1

Input
mass = 17, asteroids = [23, 9, 41, 5, 62]
Output
true

Going lightest first, the snowball reaches 22, then 31, then 54, then 95, then 157, and nothing was ever too heavy for it.

Example 2

Input
mass = 2, asteroids = [1, 4, 9]
Output
false

Taking the 1 first brings the snowball to 3, which is not enough for the 4, so the run cannot be completed. Note that with a 4 it would have reached 7 and then managed the 9, so the order matters.

Example 3

Input
mass = 4, asteroids = [4, 8, 16, 32, 64]
Output
true

Each clump exactly matches the weight the snowball has reached, and matching is enough, so it doubles its way through all five.

Constraints

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

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def asteroids_destroyed(mass: int, asteroids: list[int]) -> bool:
Java
public boolean asteroidsDestroyed(int mass, int[] asteroids)

More on the same topics