Introduction

The Asteroid Collision problem involves simulating collisions between moving asteroids.

Rules:

Positive value  → moving rightNegative value → moving left

Collision occurs when:

  • right-moving asteroid
  • meets left-moving asteroid

The smaller asteroid explodes.
If both are equal:

  • both explode

Example:

Input:[5,10,-5]

Output:
[5,10]

Explanation:

10 and -5 collide
10 is larger
-5 explodes

Remaining:
[5,10]

This problem is one of the most important applications of:

Stack Data Structure

Constraints

2 <= asteroids.length <= 10^5-1000 <= asteroids[i] <= 1000
asteroids[i] != 0

Approach 1 : Brute Force (Repeated Collision Simulation)

Explanations:

Explanation:

The idea is:

  • repeatedly scan array
  • detect collisions
  • remove exploded asteroids
  • continue until stable

Steps:

  1. Traverse array.
  2. Detect opposite directions.
  3. Compare sizes.
  4. Remove smaller asteroid.
  5. Repeat traversal.

This approach becomes inefficient because:

  • repeated scanning
  • array rebuilding
  • multiple traversals

So stack-based solution is preferred.

Dry Run

Input: [5,10,-5]

Step 1:
10 and -5 collide
10 survives

Array:
[5,10]

Final Output:
[5,10]

Practice :

Complexity Analysis :

Time Complexity:- O(n²)Explanation :
Repeated traversals and array rebuilding occur.

Space Complexity:- O(n)
Explanation :
Extra temporary array is used.

Approach 2 : Optimal Solution(Using Stack)

Explanations:

Explanation:

This is the most optimized and interview-preferred solution.

The idea is:

  • use stack to track surviving asteroids
  • collision occurs when:
    • top asteroid moves right
    • current asteroid moves left

Rules:

  • smaller asteroid explodes
  • equal sizes destroy both

This efficiently simulates collisions in one traversal.

Dry Run

Input:[5,10,-5]

Step 1:
Push 5

Stack:
[5]

Step 2:
Push 10

Stack:
[5,10]

Step 3:
Current asteroid:
-5

Collision with 10
10 survives

Stack:
[5,10]

Final Output:
[5,10]

Practice :

Complexity Analysis :

Time Complexity:- O(n)Explanation :
Each asteroid is pushed and popped at most once.

Space Complexity:- O(n)
Explanation :
Stack stores surviving asteroids.

Why This Problem is Important

This problem builds the foundation for:

  • Stack simulation
  • Collision handling
  • Direction-based traversal
  • State management
  • Array processing techniques

Real-World Applications

Asteroid Collision concepts are used in:

  • Physics simulations
  • Game engines
  • Collision detection systems
  • Traffic simulations
  • Event processing systems

Common Beginner Mistakes

  • Incorrect collision condition
  • Forgetting equal-size collision
  • Wrong stack comparisons
  • Missing repeated collisions
  • Incorrect survivor handling

Interview Tip

Interviewers often expect:

  • proper stack simulation
  • correct collision logic
  • O(n) optimization
  • repeated collision handling

Always explain:

  • why stack represents active asteroids
  • how collisions are resolved efficiently

Related Questions

  • Car Fleet
  • Daily Temperatures
  • Next Greater Element
  • Remove Adjacent Duplicates
  • Monotonic Stack Problems

Final Takeaway

The Asteroid Collision problem is one of the most important advanced stack simulation problems.

It teaches:

  • collision processing
  • stack traversal
  • repeated condition handling
  • efficient simulation logic

Understanding this problem builds a strong foundation for:

  •  simulation problems
  • advanced stack concepts
  • interview-level collision handling.