Asteroid Collision

Monotonic stack of survivors

time O(n)space O(n)

The only pair that can ever collide is a right-mover with a left-mover somewhere to its right — two asteroids going the same way never close the gap, and a left-mover followed by a right-mover only drift apart. That is exactly a stack: push every asteroid that has nothing left to fight, and when a left-mover arrives let it fight down the stack while the top is a right-mover. Each comparison ends one asteroid, so the total work is linear even though a single asteroid can clear the whole stack. Three outcomes matter: the top is smaller and gets popped so the fight continues, the top is the same size so both die, or the top is bigger so only the newcomer dies. Anything that survives its fight, or never had one, goes on the stack and the final stack is the answer in order.

Details

Animated on: asteroids = [5, 10, -5, -10, -3, 2, -9, 4] — the sign is the direction (positive flies right, negative flies left) and the magnitude is the size. When two collide the smaller one is destroyed; equal sizes destroy both. Answer: [-9, 4].

Problem:Asteroid CollisionMedium

Monotonic stack of survivors

step 1 / 10

[0]

[1]

-5

[2]

-10

[3]

-3

[4]

[5]

-9

[6]

[7]

8 asteroids, all moving at the same speed: a positive value flies RIGHT, a negative one flies LEFT. Two asteroids can only meet when a right-mover sits to the LEFT of a left-mover, so keep the survivors so far on a stack and let each new asteroid fight its way down it.

Pseudocode

1FUNCTION asteroidCollision(A):
2  stack <- EMPTY
3  FOR i <- 0 TO LENGTH(A) - 1:
4    a <- A[i]
5    WHILE a < 0 AND stack NOT EMPTY AND TOP(stack) > 0 AND TOP(stack) < -a:
6      POP stack
7    IF a < 0 AND stack NOT EMPTY AND TOP(stack) > 0:
8      IF TOP(stack) = -a:
9        POP stack
10    ELSE:
11      PUSH a ONTO stack
12  RETURN stack

← / → step · space play · Home restart

Every step in words

Show all 10 steps

8 asteroids, all moving at the same speed: a positive value flies RIGHT, a negative one flies LEFT. Two asteroids can only meet when a right-mover sits to the LEFT of a left-mover, so keep the survivors so far on a stack and let each new asteroid fight its way down it.
A[0]=5 moves RIGHT, so it can only ever be hit by something that comes LATER. Nothing to decide yet — park it on the stack. Stack: [5].
A[1]=10 moves RIGHT, so it can only ever be hit by something that comes LATER. Nothing to decide yet — park it on the stack. Stack: [5, 10].
A[2]=-5 runs into A[1]=10. 10 is bigger than 5, so the left-mover is the one that explodes and the 10 keeps flying right, still waiting for a bigger challenger. Stack: [5, 10].
A[3]=-10 meets A[1]=10 head-on and they are the SAME size 10, so both are destroyed. Neither goes on the stack. Stack: [5].
A[4]=-3 runs into A[0]=5. 5 is bigger than 3, so the left-mover is the one that explodes and the 5 keeps flying right, still waiting for a bigger challenger. Stack: [5].
A[5]=2 moves RIGHT, so it can only ever be hit by something that comes LATER. Nothing to decide yet — park it on the stack. Stack: [5, 2].
A[6]=-9 is bigger than every right-mover it met: it destroyed A[5]=2, then A[0]=5. Nothing moving right is left in front of it, so it survives all the way to the bottom. Stack: [-9].
A[7]=4 moves RIGHT, so it can only ever be hit by something that comes LATER. Nothing to decide yet — park it on the stack. Stack: [-9, 4].
Every asteroid has been offered to the stack, so no pair is still approaching each other: the ones left are A[6]=-9, A[7]=4. Answer: [-9, 4].

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Asteroid Collision in the editor All Stack problems Back to roadmap