Collision simulation

40 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Asteroids move along a line: 5, 10, −5, −11, 3. A positive number moves right, a negative one moves left, and the size is the absolute value. When two meet, the smaller explodes; equal sizes both explode. Which asteroids survive?

By hand you simulate: 5 and 10 both move right, so they never meet. −5 moves left into 10 and explodes. −11 moves left into 10, which explodes, then into 5, which explodes. 3 moves right behind −11 and never meets it. Survivors: −11, 3.

Simulating time step by step would be hopeless: positions are continuous and collisions can cascade. What you actually did was notice that only one kind of meeting is possible: a right-mover that is already to the left of a newly arriving left-mover. Everything else never meets.

Build the structure, one piece at a time

Piece one: process asteroids left to right and keep a stack of survivors so far. Anything moving left on the stack has nothing to its left that can ever reach it, so it is safe. Anything moving right on the stack might still be hit by a left-mover that arrives later.

Piece two: when a new asteroid arrives, if it moves right, or if the top of the stack moves left, there is no collision: push it. If it moves left and the top moves right, they collide. Resolve the collision: the smaller one disappears. If the newcomer wins, pop the top and check again against the new top, because the newcomer keeps travelling left. If the top wins, the newcomer is gone. If they are equal, both are gone.

The same "newcomer fights the top until settled" loop appears in car fleets (a faster car behind a slower one joins its fleet), in robots walking a corridor, and in a typed string with deletes.

Why it is correct

The invariant: the stack holds exactly the survivors among the asteroids processed so far, in order, and no two of them can ever collide. The second half is the important one. Two stack members cannot collide if the left one moves left, or the right one moves right, or both move away from each other; the only colliding arrangement is a right-mover to the left of a left-mover, and the loop never leaves that arrangement on the stack, because a left-moving newcomer fights every right-mover on top until one of them is gone or the top moves left. Processing in position order is what makes the stack top the correct opponent: the newcomer meets the nearest surviving right-mover first, and that is the most recently pushed one.

Could an asteroid that was popped have survived in reality? It was destroyed by a bigger left-mover that was definitely going to reach it, since nothing between them survived. So every pop is a real destruction and every push a real survival.

Why it is fast

Each asteroid is pushed at most once and popped at most once. A single newcomer may cause many pops, but the pops are paid for by the earlier pushes:

total stack operations ≤ 2n, so O(n) time

with O(n) space. A time-step simulation would have no such bound.

How to recognise it in an interview

Cues: "collide", "destroyed", "moving toward each other", "fleet", "the later one cancels the earlier one". The tell is that interactions only happen between a newcomer and the most recent surviving element, which is exactly what a stack top is. Say: "I will process in order with a stack of survivors; a newcomer fights the top until it is destroyed or no longer collides."

Asteroid Collision is the example. Car Fleet sorts cars by position, computes each car's time to the target, and uses the stack to merge a car into the fleet ahead when it would arrive sooner. Clear Digits pushes letters and pops the top letter whenever a digit arrives.

02The idea in one line

Push moving things; when a newcomer collides with the top, resolve and maybe keep popping.

Reach for it when: Asteroid collision, car fleets, robot crashes, meeting of opposite movers.

Cost: O(n) time.

03The walk-through, step by step

The video works one example: Asteroid Collision on [5,10,-5,-11,3]. These are its captions in order, so you can follow without the video or check a step you missed.

1. Only a right-mover on the stack can hit a new left-mover
2. Next asteroid 5 (right)
3. No collision: push 5
4. Next asteroid 10 (right)
5. No collision: push 10
6. Next asteroid -5 (left)
7. -5 hits 10: 10 is bigger, -5 explodes
8. Next asteroid -11 (left)
9. -11 hits 10: 11 > 10, 10 explodes, keep checking
10. -11 hits 5: 11 > 5, 5 explodes, keep checking
11. No collision: push -11
12. Next asteroid 3 (right)
13. No collision: push 3
14. Survivors: [−11, 3]
15. Each asteroid is pushed once and popped at most once: O(n)

04Asked at Google

5 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Stack: Matching with a stack, Nested structure via stack, Expression evaluation, Auxiliary-min stack.