Skip to main content
Talentd

Destroying Asteroids - Solution & Explanation

MediumArrayGreedySorting16 min readAsked at: Google
Practice this problem

Problem Statement

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

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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

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.

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.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(n log n), dominated by the heap operations.
Space Complexity: O(n) for storing the heap.

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Sorting and Sequential Processing

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.

Approach 2: Priority Queue for Dynamic Ordering

Time Complexity: O(n log n), dominated by the heap operations.
Space Complexity: O(n) for storing the heap.

Sorting + Greedy—

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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.

Video Solution

Destroying Asteroids | Simple Approach | Dry Run | Leetcode 2126 | codestorywithMIK • codestorywithMIK • 4,256 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Destroying Asteroids with our built-in code editor and test cases.

Practice on FleetCode
Previous

Asteroid Collision