Pattern visualizer
Asteroid Collision
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. 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]..
Monotonic stack of survivors
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.
1FUNCTION asteroidCollision(A):2 stack <- EMPTY3 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 stack7 IF a < 0 AND stack NOT EMPTY AND TOP(stack) > 0:8 IF TOP(stack) = -a:9 POP stack10 ELSE:11 PUSH a ONTO stack12 RETURN stack
← / → step · space play · Home restart