visual walkthrough
Asteroid Collision
Collision rules make you think about exactly when to pop.
The idea
Asteroids only collide when a right-mover is immediately followed by a left-mover. The stack holds the survivors; a new left-mover fights the right-mover on top, destroying smaller ones until it is destroyed itself or reaches safety.
Everything else (a right-mover, or a left-mover with nothing moving right before it) just joins the stack.
Complexity
| approach | time | space |
|---|---|---|
| Find a collision, repeat | O(n²) | O(n) |
| Stack of survivors | O(n) | O(n) |