Destroying Asteroids solution and explanation
Google
9 more videos on this problem
Destroying Asteroids | Simple Approach | Dry Run | Leetcode 2126 | codestorywithMIKcodestorywithMIK · 11:50 · 4K views
2126. Destroying Asteroids (Leetcode Medium)Programming Live with Larry · 8:49 · 437 views
Destroying Asteroids | LEETCODE - 2126 | Easy solutionhi-malik · 5:47 · 320 views
2126. Destroying Asteroids | Leetcode Daily - PythonLeetcode Daily · 5:08 · 294 views
Destroying Asteroids | LeetCode 2126 - Pythonimpoldev · 4:45 · 166 views
Leetcode 2126. Destroying AsteroidsElite Code · 16:24 · 156 views
Destroying Asteroids | LeetCode 2126 | Greedy | Java Code | Developer CoderDeveloper Coder · 6:26 · 140 views
Explaining Leetcode - #2126 Destroying Asteroids (Medium)JTECH · 9:26 · 77 views
Leetcode 2126. Destroying AsteroidsExpertFunda · 11:46 · 74 views
2126. Destroying Asteroids Leetcode Daily challenge #coding #python #learning #dayoneMuthu Vrn · 0:46 · 69 views
The 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 <= 1051 <= asteroids.length <= 1051 <= asteroids[i] <= 105
Approach overview
Problem 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.
Approach 1: Approach 1: Sorting and Sequential Processing
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:
- Sort the asteroid array in ascending order.
- Iterate through the sorted array, checking if the current mass of the planet is >= the asteroid's mass.
- If true, add the asteroid's mass to the planet's mass.
- Stop and return false if any asteroid has greater mass than the planet.
- Return true if all asteroids are processed successfully.
def can_destroy_asteroids(mass, asteroids):
asteroids.sort()
for asteroid in asteroids:
if mass >= asteroid:
mass += asteroid
else:
return False
return True
# Example usage
mass = 10
asteroids = [3, 9, 19, 5, 21]
print(can_destroy_asteroids(mass, asteroids))import java.util.Arrays;
class Solution {
public boolean canDestroyAsteroids(int mass, int[] asteroids) {
Arrays.sort(asteroids);
for (int asteroid : asteroids) {
if (mass >= asteroid) {
mass += asteroid;
} else {
return false;
}
}
return true;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] asteroids = {3, 9, 19, 5, 21};
int mass = 10;
System.out.println(solution.canDestroyAsteroids(mass, asteroids));
}
}#include <vector>
#include <algorithm>
bool canDestroyAsteroids(int mass, std::vector<int>& asteroids) {
std::sort(asteroids.begin(), asteroids.end());
for (int asteroid : asteroids) {
if (mass >= asteroid) {
mass += asteroid;
} else {
return false;
}
}
return true;
}
#include <iostream>
int main() {
std::vector<int> asteroids = {3, 9, 19, 5, 21};
int mass = 10;
std::cout << (canDestroyAsteroids(mass, asteroids) ? "true" : "false") << std::endl;
return 0;
}function canDestroyAsteroids(mass, asteroids) {
asteroids.sort((a, b) => a - b);
for (let asteroid of asteroids) {
if (mass >= asteroid) {
mass += asteroid;
} else {
return false;
}
}
return true;
}
console.log(canDestroyAsteroids(10, [3, 9, 19, 5, 21]));#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int *)a - *(int *)b);
}
bool canDestroyAsteroids(int mass, int *asteroids, int asteroidsSize) {
qsort(asteroids, asteroidsSize, sizeof(int), compare);
for (int i = 0; i < asteroidsSize; i++) {
if (mass >= asteroids[i]) {
mass += asteroids[i];
} else {
return false;
}
}
return true;
}
int main() {
int asteroids[] = {3, 9, 19, 5, 21};
int mass = 10;
int size = sizeof(asteroids) / sizeof(asteroids[0]);
printf("%s\n", canDestroyAsteroids(mass, asteroids, size) ? "true" : "false");
return 0;
}using System;
class Solution {
public bool CanDestroyAsteroids(int mass, int[] asteroids) {
Array.Sort(asteroids);
foreach (int asteroid in asteroids) {
if (mass >= asteroid) {
mass += asteroid;
} else {
return false;
}
}
return true;
}
public static void Main(string[] args) {
Solution solution = new Solution();
int[] asteroids = {3, 9, 19, 5, 21};
int mass = 10;
Console.WriteLine(solution.CanDestroyAsteroids(mass, asteroids));
}
}The Python solution uses Python's built-in sort() to order the asteroids. It then follows a simple iteration and accumulation process to assess whether all asteroids can be destroyed in the sorted sequence.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) additional space, apart from input storage, is utilized.
Approach 2: Approach 2: Priority Queue for Dynamic Ordering
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:
- Insert all asteroid masses into a min-heap (priority queue).
- While the heap is not empty, extract the minimum (smallest mass asteroid).
- Check if the planet's mass is sufficient to destroy the asteroid; if so, update the planet's mass.
- If an asteroid's mass is greater than the planet's current mass, return false.
- If the heap is exhausted and all asteroids are destroyed, return true.
import heapq
def can_destroy_asteroids_heap(mass, asteroids):
heapq.heapify(asteroids)
while asteroids:
smallest = heapq.heappop(asteroids)
if mass >= smallest:
mass += smallest
else:
return False
return True
# Example usage
mass = 10
asteroids = [3, 9, 19, 5, 21]
print(can_destroy_asteroids_heap(mass, asteroids))import java.util.PriorityQueue;
class SolutionPriorityQueue {
public boolean canDestroyAsteroids(int mass, int[] asteroids) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int asteroid : asteroids) {
minHeap.offer(asteroid);
}
while (!minHeap.isEmpty()) {
int smallest = minHeap.poll();
if (mass >= smallest) {
mass += smallest;
} else {
return false;
}
}
return true;
}
public static void main(String[] args) {
SolutionPriorityQueue solution = new SolutionPriorityQueue();
int[] asteroids = {3, 9, 19, 5, 21};
int mass = 10;
System.out.println(solution.canDestroyAsteroids(mass, asteroids));
}
}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.
Approach 3: Sorting + Greedy
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.
function asteroidsDestroyed(mass: number, asteroids: number[]): boolean {
asteroids.sort((a, b) => a - b);
for (const x of asteroids) {
if (mass < x) {
return false;
}
mass += x;
}
return true;
}func asteroidsDestroyed(mass int, asteroids []int) bool {
sort.Ints(asteroids)
for _, x := range asteroids {
if mass < x {
return false
}
mass += x
}
return true
}impl Solution {
pub fn asteroids_destroyed(mass: i32, mut asteroids: Vec<i32>) -> bool {
let mut mass = mass as i64;
asteroids.sort_unstable();
for &x in &asteroids {
if mass < x as i64 {
return false;
}
mass += x as i64;
}
true
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Sorting and Sequential Processing | Time Complexity: O(n log n) due to sorting. |
| Approach 2: Priority Queue for Dynamic Ordering | Time Complexity: O(n log n), dominated by the heap operations. |
| Sorting + Greedy | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Destroying Asteroids easy or hard?
Destroying Asteroids is classified as a Medium problem on LeetCode. The coding itself is straightforward, but recognizing the greedy insight—destroying smaller asteroids first by sorting the array—is the key step that makes the solution work efficiently.
Destroying Asteroids Python/Java solution
Most implementations sort the asteroid list and iterate while tracking the current mass. Python solutions typically use list sorting with a loop, while Java solutions rely on Arrays.sort followed by iteration. Both implementations achieve O(n log n) time and handle very large mass values using 64-bit integers.
How to solve Destroying Asteroids in O(n)?
A strict O(n) solution is generally not possible because the greedy strategy requires processing asteroids from smallest to largest. That ordering requires sorting or a priority queue, both of which cost O(n log n). Only special constraints like a small bounded value range would allow linear-time counting sort.
What is the best approach for Destroying Asteroids?
The most efficient approach is a greedy strategy combined with sorting. Sort the asteroid masses in ascending order and iterate through them while accumulating mass. If the current mass is always greater than or equal to the asteroid you encounter, you can destroy all asteroids. This runs in O(n log n) time due to sorting and O(1) extra space if sorting is done in place.
Is Destroying Asteroids asked at Google/Amazon/Meta?
Destroying Asteroids is a typical greedy interview problem seen on platforms preparing candidates for companies like Amazon, Google, and Meta. While the exact question may vary, the pattern of sorting inputs and greedily accumulating resources appears frequently in real interview problems.
What data structure is used in Destroying Asteroids?
The primary data structure is an array combined with sorting to enforce ascending order processing. An alternative implementation uses a min-heap priority queue to repeatedly extract the smallest asteroid. Both approaches rely on the greedy idea of always consuming the smallest available obstacle first.
What is the time complexity of Destroying Asteroids?
The optimal solution runs in O(n log n) time because the asteroid array must be sorted before processing. After sorting, a single linear pass checks whether the planet can absorb each asteroid, which costs O(n). Space complexity ranges from O(1) to O(n) depending on the sorting implementation.