Introduction

LeetCode 2126 – Destroying Asteroids is a classic greedy algorithm problem that tests your ability to:

1. Recognize optimal ordering
2. Use sorting effectively
3. Apply greedy decision-making
4. Handle large integer growth
5. Understand simulation problems

This is a very interview-friendly problem because the optimal strategy is not immediately obvious.

Problem Link

🔗 https://leetcode.com/problems/destroying-asteroids/

Problem Statement

You are given:

1. An integer mass representing the planet’s initial mass
2. An array asteroids

Rules:

1. If planet mass ≥ asteroid mass → asteroid is destroyed
2. Planet gains asteroid mass
3. Otherwise → planet gets destroyed

Return:

Example

Input

Output

Key Observation

The most important insight:

Destroy smaller asteroids first.

Why?

Because every destroyed asteroid increases planet mass.

So destroying smaller asteroids early helps you grow enough to destroy larger ones later.

Intuition

Suppose:

If you attack:

You instantly lose.

But if you destroy:

Your mass becomes:

Still not enough for 100.

So answer remains false.

This demonstrates:

Ordering matters.

Greedy Strategy

The optimal strategy is:

Step 1

Sort asteroids in ascending order.

Step 2

Destroy the smallest asteroid possible first.

Step 3

Keep increasing mass.

Why Sorting Works

If you cannot destroy the smallest remaining asteroid:

That is why sorting guarantees the optimal greedy order.

Java Solution

Cleaner Optimized Version

One important improvement:

Use long instead of int.

Why?

Because mass can grow very large.

Optimized Java Solution

Why Use Long?

Constraints allow:

Mass can exceed:

Using long prevents overflow issues.

Dry Run

Input

Step 1: Sort

Step 2: Destroy Asteroids

Destroy 3

Destroy 5

Destroy 9

Destroy 19

Destroy 21

All asteroids destroyed.

Final Output

Brute Force Approach

A brute force approach would try:

This means:

Which is impossible for:

So brute force is completely infeasible.

Why Greedy Is Optimal

Greedy works because:

1. Smaller asteroids are easiest to destroy
2. They increase mass
3. Increased mass helps destroy bigger asteroids

This creates a natural optimal progression.

Time Complexity Analysis

Sorting

Traversal

Total Time Complexity

Space Complexity

Ignoring sorting space.

Interview Explanation

In interviews, explain:

Since destroying an asteroid increases our mass, the optimal strategy is to destroy smaller asteroids first. Sorting ensures we always maximize future growth opportunities.

This demonstrates:

1. Greedy thinking
2. Sorting optimization
3. Simulation handling
4. Proof of correctness

Common Mistakes

1. Not Sorting

Without sorting:

2. Using int Instead of long

Mass can overflow.

Always use:

3. Brute Force Permutations

Trying all orders leads to:

which is impossible.

4. Incorrect Early Return

Your logic should only fail when:

FAQs

Q1. Why is sorting necessary?

Sorting guarantees we always destroy the smallest possible asteroid first.

Q2. Is this a greedy problem?

Yes.

The optimal local decision:

leads to global optimality.

Q3. Why use long?

Because mass can grow beyond integer limits.

Q4. Is this asked in interviews?

Yes.

It is a common greedy + sorting interview problem.

Conclusion

LeetCode 2126 is an excellent greedy problem for mastering:

1. Sorting-based optimization
2. Greedy decision-making
3. Simulation problems
4. Overflow handling
5. Interview reasoning

The key insight is:

Always destroy smaller asteroids first to maximize future mass growth.

Once this greedy intuition becomes natural, many scheduling and optimization problems become easier to solve.