Asteroid Collision
Simulate asteroid collisions where absolute value is size and sign is direction (+ right, - left).
- 2 <= asteroids.length <= 10⁴
- -1000 <= asteroids[i] <= 1000
- asteroids[i] != 0
asteroids = [5,10,-5][5,10]asteroids = [10,2,-5][10]asteroids = [8,-8][]Two asteroids can only collide when a right-moving one (positive) sits somewhere to the left of a left-moving one (negative) — they close the gap between them. Two right-movers never catch each other, and two left-movers drift apart forever. So the only interesting moment is a negative asteroid meeting the right-movers ahead of it.
The thing that makes a stack the natural fit is which asteroid a left-mover hits first: the most recently added surviving right-mover — the one nearest to it. And if that collision destroys the right-mover, the left-mover keeps travelling and immediately meets the next most recent survivor, and so on. "Deal with the most recent survivor, and if it's gone, fall back to the one before it" is exactly last-in-first-out, which is what a stack gives you. Keep a stack of everything that has survived so far, in order; each incoming asteroid either passes through quietly or triggers a short chain of collisions off the top.
For each asteroid: if it's moving right, or the stack has nothing to its left that could hit it, it just survives onto the stack. If it's moving left, run it against the right-movers on top:
- top is smaller → the top explodes (pop), and our asteroid keeps going to meet whatever's beneath;
- top is equal in size → both explode;
- top is bigger → our asteroid explodes and the stack is untouched.
Only if it clears every right-mover in its path (stack empties, or the next survivor is itself a left-mover) does it land on the stack as a survivor.
def asteroid_collision(asteroids):
stack = []
for a in asteroids:
alive = True
# only a left-mover meeting a right-mover on top can collide
while alive and a < 0 and stack and stack[-1] > 0:
top = stack[-1]
if top < -a:
stack.pop() # top is smaller: it explodes, 'a' travels on
elif top == -a:
stack.pop() # equal size: both explode
alive = False
else:
alive = False # top is bigger: 'a' explodes
if alive:
stack.append(a)
return stackEvery asteroid is pushed at most once and popped at most once, so the whole chain-reaction simulation runs in one linear pass.
10 → moves right, survives. Stack: [10]2 → moves right, survives. Stack: [10, 2]-5 → hits top 2: size 5 > 2, the 2 explodes → [10]. Now hits 10: size 5 < 10, so -5 explodes and 10 stands.[10].Stack-based multi-collision chain reaction
Mental Model
- Stack as History: The stack tracks asteroids currently flying Right (+). They are the potential targets for incoming Left (-) asteroids.
- Cascading Collisions: A single incoming (-) asteroid can trigger a chain reaction, destroying multiple (+) asteroids in the stack until it meets its match or survives.
- Momentum: (-, +) never collide because they are already moving away from each other. (+, -) is the only collision case.
Interaction Physics
1. Positive (+) flies Right. 2. Negative (-) flies Left. 3. Larger Mass survives. 4. If Equal Mass, both are destroyed. 5. Only Right-Left pairs collide.