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] <= 105Problem Overview: You start with a planet of mass mass and a list of asteroid masses. If your planet's mass is greater than or equal to an asteroid, you destroy it and your mass increases by that asteroid’s mass. If you encounter an asteroid larger than your current mass, the process stops. The goal is to determine whether you can destroy every asteroid.
Approach 1: Sorting and Sequential Processing (Greedy) (Time: O(n log n), Space: O(1) or O(n) depending on sort)
This approach relies on a greedy observation: always destroy the smallest asteroid first so your mass grows as quickly as possible. Start by sorting the asteroid array in ascending order using a standard sorting algorithm. Then iterate through the sorted list and check whether the current asteroid mass is less than or equal to your planet’s mass. If it is, add the asteroid’s mass to your total and continue; otherwise return false immediately. Sorting ensures you never face a large asteroid before accumulating enough mass, which makes the greedy choice optimal. The runtime is dominated by sorting at O(n log n), while the scan itself is O(n). This approach works well because the problem reduces to processing values in increasing order using simple arithmetic on an array.
Approach 2: Priority Queue for Dynamic Ordering (Time: O(n log n), Space: O(n))
Instead of sorting the array up front, you can push all asteroid masses into a min-heap (priority queue). Each step extracts the smallest asteroid currently available. If your mass is large enough, absorb it and increase your mass; otherwise stop and return false. The heap always gives the smallest remaining asteroid, which preserves the same greedy property as the sorting solution. Each insertion and extraction costs O(log n), so processing all asteroids results in O(n log n) time with O(n) additional memory. This method is useful when values may be streamed or dynamically inserted, since the heap maintains order without a full re-sort. It demonstrates how greedy strategies can be combined with a priority queue for incremental ordering.
Recommended for interviews: The sorting-based greedy approach is what interviewers typically expect. It shows you recognize the key insight: destroying smaller asteroids first maximizes growth and avoids early failure. Implementing the sorted iteration is straightforward and communicates strong problem-solving instincts. The priority queue variation is a good follow-up discussion that shows you understand alternative data structures and dynamic ordering tradeoffs.
Idea: By sorting the asteroids in ascending order based on their mass, we can ensure that the planet gains mass in the most efficient manner. Starting from the smallest, the planet's mass increases more rapidly, allowing it to destroy larger asteroids in sequence.
Steps:
This C solution first sorts the asteroid array using qsort. It then iterates through the sorted array, maintaining the planet's mass and checking if it is sufficient to destroy each asteroid. If at any point an asteroid cannot be destroyed, it returns false.
Time Complexity: O(n log n) due to sorting, where n is the number of asteroids.
Space Complexity: O(1) as no additional space is required apart from input storage.
Idea: By utilizing a priority queue (or min-heap), we can dynamically handle the asteroid mass destruction process, ensuring that we always target the smaller asteroids first without needing to fully sort the array.
Steps:
This Python solution uses the heapq library to manage the asteroid masses in a heap, facilitating the extraction of the smallest item in logarithmic time. The while-loop checks if each extracted mass can be absorbed by the planet, ensuring that if any asteroid exceeds the current mass, the function returns false.
Time Complexity: O(n log n), dominated by the heap operations.
Space Complexity: O(n) for storing the heap.
According to the problem description, we can sort the asteroids by mass in ascending order, and then iterate through the asteroids. If the planet's mass is less than the asteroid's mass, the planet will be destroyed, and we return false. Otherwise, the planet will gain the mass of the asteroid.
If all asteroids can be destroyed, return true.
The time complexity is O(n times log n), and the space complexity is O(log n). Where n is the number of asteroids.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
| Approach | Complexity |
|---|---|
| Approach 1: Sorting and Sequential Processing | Time Complexity: O(n log n) due to sorting, where n is the number of asteroids. |
| Approach 2: Priority Queue for Dynamic Ordering | Time Complexity: O(n log n), dominated by the heap operations. |
| Sorting + Greedy | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting and Sequential Processing (Greedy) | O(n log n) | O(1) to O(n) | Best general solution. Simple implementation when the full array is available. |
| Priority Queue (Min Heap) | O(n log n) | O(n) | Useful if asteroids arrive dynamically or when maintaining smallest-first ordering incrementally. |
Medium Google Interview Question! - Destroying Asteroids - Leetcode 2126 • Greg Hogg • 118,122 views views
Watch 9 more video solutions →Practice Destroying Asteroids with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor