# Destroying Asteroids
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/destroying-asteroids)
Canonical: https://scaleengineer.com/dsa/problems/destroying-asteroids
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## 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` _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 <= 105`
* `1 <= asteroids.length <= 105`
* `1 <= asteroids[i] <= 105`

# Approaches
## Brute Force by Generating All Permutations
This approach involves testing every single possible sequence of collisions. It generates all permutations of the `asteroids` array and, for each permutation, simulates the collision process to see if the planet can survive and destroy all asteroids in that specific order. If any valid order is found, the function returns `true`.
**Time:** O(N! * N). There are N! permutations to check. For each permutation, we iterate through N asteroids. This is computationally infeasible for the given constraints. · **Space:** O(N^2). The recursion depth can go up to N, and at each level, a new list of remaining asteroids is created, which can have up to N elements.
**Pros:** Conceptually simple and guaranteed to find a solution if one exists, given infinite time.
**Cons:** Extremely inefficient with a time complexity of O(N! * N).; Not feasible for the given constraints and will cause a 'Time Limit Exceeded' error for anything but very small inputs (N > 10).
### Explanation
The brute-force method systematically checks every single ordering of the asteroids. This can be implemented using a recursive backtracking algorithm. The function would try to destroy each available asteroid, and if successful, recurse with the updated planet mass and the remaining asteroids. If a path is found where all asteroids are destroyed, we have our answer. However, the number of possible orderings is N! (N factorial), which grows incredibly fast, making this solution impractical for the problem's constraints.

```java
import java.util.ArrayList;
import java.util.List;

// NOTE: This solution is for demonstration purposes and will Time Limit Exceed.
class Solution {
    public boolean asteroidsDestroyed(int mass, int[] asteroids) {
        List<Integer> asteroidList = new ArrayList<>();
        for (int a : asteroids) {
            asteroidList.add(a);
        }
        // Using a long for mass to be safe, though it won't save the performance.
        return canDestroy(mass, asteroidList);
    }

    private boolean canDestroy(long currentMass, List<Integer> remainingAsteroids) {
        // Base case: all asteroids have been destroyed.
        if (remainingAsteroids.isEmpty()) {
            return true;
        }

        // Try to destroy each of the remaining asteroids.
        for (int i = 0; i < remainingAsteroids.size(); i++) {
            int asteroidMass = remainingAsteroids.get(i);
            
            // Check if the planet can destroy this asteroid.
            if (currentMass >= asteroidMass) {
                // Create the next state.
                List<Integer> nextRemaining = new ArrayList<>(remainingAsteroids);
                nextRemaining.remove(i);
                
                // Recurse.
                if (canDestroy(currentMass + asteroidMass, nextRemaining)) {
                    return true; // Found a valid path.
                }
            }
        }
        
        // No asteroid could be destroyed in a way that leads to a solution.
        return false;
    }
}
```
### Algorithm
- Define a recursive function that explores all possible orderings of asteroids.
- The function takes the current mass and the list of remaining asteroids as parameters.
- **Base Case:** If the list of remaining asteroids is empty, it means all have been destroyed, so return `true`.
- **Recursive Step:** Iterate through each asteroid in the remaining list.
- If the current mass is sufficient to destroy the selected asteroid (`currentMass >= asteroidMass`):
  - Make a recursive call with the updated mass (`currentMass + asteroidMass`) and a new list of asteroids (with the current one removed).
  - If the recursive call returns `true`, propagate this result up by returning `true`.
- If the loop completes without finding any successful path, it means no asteroid can be destroyed from the current state, so return `false`.
- If all permutations are tried and none succeed, the final result is `false`.

## Greedy Approach with Sorting
This is an efficient and optimal greedy approach. The core idea is that to maximize the chances of destroying larger asteroids, the planet should first accumulate as much mass as possible by destroying the smallest asteroids. By sorting the asteroids by mass and processing them in that order, we follow the most optimal strategy. If this strategy fails, no other order can succeed.
**Time:** O(N log N). The dominant operation is sorting the `asteroids` array. The subsequent linear scan takes O(N) time. · **Space:** O(log N) or O(N). This depends on the space used by the sorting algorithm. In Java, `Arrays.sort()` for primitive types uses a dual-pivot quicksort, which requires O(log N) space on average for the recursion stack. In the worst case, it could be O(N).
**Pros:** Highly efficient with O(N log N) time complexity, which is optimal.; Simple to understand and implement.; Correctly solves the problem for all cases within the given constraints.
**Cons:** The approach requires sorting, which takes O(N log N) time.; It either modifies the input array in-place or requires O(N) extra space for a copy if the original array must be preserved.
### Explanation
The key insight for an optimal solution is to realize that a greedy strategy works. To maximize our ability to destroy larger asteroids later, we should first destroy the smallest asteroids we can. This increases the planet's mass as much as possible at each stage. Therefore, the best strategy is to sort the asteroids by mass and attempt to destroy them in ascending order.

If the planet's mass is ever insufficient for the next-smallest asteroid, it will certainly be insufficient for any subsequent, larger asteroids. In this case, we can conclude that it's impossible to destroy them all. If we successfully iterate through the entire sorted list, we have proven that all asteroids can be destroyed.

It's important to use a `long` data type for the planet's mass, as the cumulative mass can exceed the capacity of a standard 32-bit integer (`Integer.MAX_VALUE`).

```java
import java.util.Arrays;

class Solution {
    public boolean asteroidsDestroyed(int mass, int[] asteroids) {
        // Sort the asteroids array to process them from smallest to largest.
        Arrays.sort(asteroids);

        // Use a long for the planet's mass to prevent potential overflow.
        long currentMass = mass;

        // Iterate through the sorted asteroids.
        for (int asteroidMass : asteroids) {
            // If the planet's mass is less than the current asteroid's mass,
            // it cannot be destroyed. Since the array is sorted, no subsequent
            // asteroid can be destroyed either.
            if (currentMass < asteroidMass) {
                return false;
            }
            // Otherwise, the asteroid is destroyed, and the planet gains its mass.
            currentMass += asteroidMass;
        }

        // If the loop completes, all asteroids were successfully destroyed.
        return true;
    }
}
```
### Algorithm
- Sort the `asteroids` array in non-decreasing order.
- Initialize a `long` variable, `currentMass`, with the initial `mass` to prevent integer overflow.
- Iterate through the sorted `asteroids` array from smallest to largest.
- For each `asteroidMass` in the array:
  - Check if `currentMass < asteroidMass`.
  - If it is, the planet cannot destroy this asteroid, and since the rest are even larger, it's impossible to succeed. Return `false`.
  - Otherwise, the planet destroys the asteroid. Update the mass: `currentMass += asteroidMass`.
- If the loop completes, it means every asteroid was successfully destroyed. Return `true`.

# Solutions
### Java

```java
class Solution {
public
  boolean asteroidsDestroyed(int mass, int[] asteroids) {
    Arrays.sort(asteroids);
    long m = mass;
    for (int v : asteroids) {
      if (m < v) {
        return false;
      }
      m += v;
    }
    return true;
  }
}

```

### JavaScript

```javascript
/** * @param {number} mass * @param {number[]} asteroids * @return {boolean} */ var asteroidsDestroyed =
  function (mass, asteroids) {
    asteroids.sort((a, b) => a - b);
    for (const x of asteroids) {
      if (mass < x) {
        return false;
      }
      mass += x;
    }
    return true;
  };

```

### Python

```python
class Solution:
    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool: asteroids . sort() for v in asteroids: if mass < v: return False mass += v return True

```

### CPP

```cpp
class Solution {
public:
  bool asteroidsDestroyed(int mass, vector<int> &asteroids) {
    sort(asteroids.begin(), asteroids.end());
    long long m = mass;
    for (int v : asteroids) {
      if (m < v)
        return false;
      m += v;
    }
    return true;
  }
};

```