Destroying Asteroids
MedPrompt
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 <= 1051 <= asteroids.length <= 1051 <= asteroids[i] <= 105
Approaches
2 approaches with complexity analysis and trade-offs.
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.
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 returningtrue.
- Make a recursive call with the updated mass (
- 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.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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).
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.
Algorithm
- Sort the
asteroidsarray in non-decreasing order. - Initialize a
longvariable,currentMass, with the initialmassto prevent integer overflow. - Iterate through the sorted
asteroidsarray from smallest to largest. - For each
asteroidMassin 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.
- Check if
- If the loop completes, it means every asteroid was successfully destroyed. Return
true.
Walkthrough
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).
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; }}Complexity
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).
Trade-offs
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.
Solutions
Solution
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; }}/** * @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; };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 Trueclass 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; }};Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.