2126. Destroying Asteroids

2126. Destroying Asteroids

Difficulty: Medium

Topics: Staff, Array, Greedy, Sorting, Weekly Contest 274

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 iᵗʰ 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.

Example 1:

• 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:

• 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⁵
• 1 <= asteroids.length <= 10⁵
• 1 <= asteroids[i] <= 10⁵

Hint:

1. Choosing the asteroid to collide with can be done greedily.
2. If an asteroid will destroy the planet, then every bigger asteroid will also destroy the planet.
3. You only need to check the smallest asteroid at each collision. If it will destroy the planet, then every other asteroid will also destroy the planet.
4. Sort the asteroids in non-decreasing order by mass, then greedily try to collide with the asteroids in that order.

Solution:

The solution determines whether a planet with a given starting mass can destroy all asteroids by colliding with them in an optimal order.

It does this by sorting the asteroids in ascending order and then greedily absorbing them one by one, ensuring the planet’s mass never drops below the next asteroid’s mass. If at any point the planet’s mass is insufficient, the answer is false; otherwise, it’s true.

Approach:

• Sorting the asteroids in non-decreasing order ensures we always try to absorb the smallest possible asteroid next.
• Greedy absorption — if the planet’s current mass is at least the asteroid’s mass, it absorbs it and increases its mass.
• Early exit — if at any step the planet’s mass is less than the asteroid’s mass, all larger asteroids will also be impossible to absorb, so we return false.
• Final check — if all asteroids are processed successfully, return true.

Let's implement this solution in PHP: 2126. Destroying Asteroids

<?php
/**
 * @param Integer $mass
 * @param Integer[] $asteroids
 * @return Boolean
 */
function asteroidsDestroyed(int $mass, array $asteroids): bool
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo asteroidsDestroyed([1, 2, 3, 10, 4, 2, 3, 5]) . "\n";      // Output: true
echo asteroidsDestroyed([5, 4, 3, 2, 1]) . "\n";                // Output: false
?>

Explanation:

• Step 1: Sort the asteroids array so the smallest asteroids come first.
  
  Reason: Absorbing smaller asteroids first maximizes the chance of reaching a mass large enough to take on bigger ones.

• Step 2: Initialize currentMass with the planet’s starting mass.
  
  Purpose: Track the planet’s mass dynamically as it absorbs asteroids.

• Step 3: Loop through each asteroid in the sorted list.
  
  Check: If currentMass >= asteroid, the planet can destroy it — add the asteroid’s mass to currentMass.
  
  Otherwise: Immediately return false (planet is destroyed).

• Step 4: If the loop completes without returning false, return true (all asteroids destroyed).

Complexity

• Time Complexity: O(n log n) due to sorting, where n is the number of asteroids. Greedy traversal is O(n).
• Space Complexity: O(1) extra space (sorting may use O(log n) stack space in PHP’s sort() function).

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

• LinkedIn
• GitHub