AlgoViz
HomeStack

Asteroid Collision

Medium

The stack holds the survivors so far

Problem

Asteroids move right (+) or left (-); equal sizes both explode, else the smaller explodes. Return the surviving asteroids.

In simple words

Use a stack; a left-moving rock fights the top right-mover, smaller ones exploding, until it's safe.

The idea

Only a right-moving asteroid on the stack can collide with a left-moving one arriving next, so push everything and resolve collisions by popping while that condition holds. Equal sizes destroy both; a bigger incoming one keeps going and may collide again.

The trick

  • A collision needs a positive on the stack and a negative arriving.
  • Equal magnitudes: pop the stack and drop the incoming asteroid.
  • Keep looping — one asteroid can destroy several.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

5
10
-5
0
1
2

Step 1 of 2. Here's the example — [5,10,-5] Values: 5, 10, -5.

1/2
Optimal
timeO(n)spaceO(n)
1stack=[]2for a in asteroids:3  while stack.top>0 and a<0: resolve collision (pop/destroy)4  if survives: push a

Input

array
[5, 10, -5]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
asteroids = [5, 10, -5]
Output:
[5, 10]
Explanation:
10 destroys the -5; 5 and 10 survive.

Example 2

Input:
asteroids = [8, -8]
Output:
[]
Explanation:
Equal sizes blow each other up → empty.

Example 3

Input:
asteroids = [-2, -1, 1, 2]
Output:
[-2, -1, 1, 2]
Explanation:
They fly apart → all survive.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.