Medium · Collision Stack
Understand → Visualise → Practice.
Positive asteroids move right and negative ones left. Return the survivors after every head-on collision.
Only a left-moving asteroid meeting a right-moving one on the stack collides. Pop smaller right-movers, destroy both on a tie, and push the newcomer if it survives.
The stack holds the asteroids that have survived so far.
While x < 0 and the top is positive: pop a smaller top; on equal size pop and destroy x; if the top is bigger, x is destroyed.
If x is still alive, push it; the stack is the answer.
O(n) time and O(n) space.
Two asteroids moving apart (left-mover then right-mover) never collide.
Read the full guides first: Stacks, Queues and Deques.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.