Asteroid Collision
Asteroids move left or right by sign, with magnitude giving size. Equal sizes destroy both; otherwise the smaller is destroyed. Return the final state.
Open on LeetCode ↗Intuition
Writing if st and st[-1] > 0 and st[-1] < -a: st.pop() looks like it handles a collision, but it only fights one round: a big left-mover that should plow through three smaller right-movers in a row stops after destroying the first one and then gets pushed on top of a survivor it should have destroyed too. The fix is while, not if — a collision only ever happens between a right-mover already in flight and a left-mover arriving behind it, and the left-mover keeps fighting backwards through the stack until it dies, ties out, or clears everything in its way and lands.
A stack holds the survivors so far. Only a left-moving asteroid meeting a right-moving one on top collides — same-direction pairs never interact. That single condition, a < 0 and st[-1] > 0, is the entire collision rule.
Approach
Identify the only collision case
Two right-movers never meet, nor do two left-movers, and a left-mover followed by a right-mover diverges. The single colliding configuration is a positive value on the stack with a negative value arriving — checking that pair is the whole simulation.
Fight backwards while the collision holds
For an incoming negative asteroid, loop while the stack top is positive and smaller in magnitude: pop it, since the incoming one wins and continues. If the top is larger, the incoming asteroid is destroyed and you stop without pushing. If magnitudes are equal, pop the top and destroy the incoming one too.
Push the survivor
If the incoming asteroid survived every fight, push it. The bug to watch is reaching for if instead of while in the collision loop above — with if, a size-10 left-mover meeting [3, 4, 5] on the stack only pops the 5, then gets appended on top of the still-alive 3 and 4, leaving three asteroids where physically only one should remain. Use a flag or a for/else to distinguish surviving from being destroyed. Each asteroid is pushed and popped at most once, so the whole thing is O(n) time and O(n) space.
Solution & live demo
Common pitfalls
Colliding same-direction asteroids
while st and abs(st[-1]) < abs(a):
while alive and a < 0 and st and st[-1] > 0:
Two asteroids moving the same way never meet, regardless of size. Without the direction check, a large left-mover destroys smaller left-movers that were never in its path.
Pushing the asteroid after an equal-size collision
elif st[-1] == -a:
st.pop()
st.append(a)elif st[-1] == -a:
st.pop()
alive = FalseEqual sizes destroy both. Popping the survivor but still pushing the newcomer leaves one asteroid where none should remain.
Using break in place of the alive flag
else:
break
st.append(a)else:
alive = False
...
if alive: st.append(a)break exits the collision loop but still falls through to the push, so an asteroid that was destroyed gets appended anyway. The flag separates "stop colliding" from "survived".
Edge cases
No collisions ever occur; the input is returned unchanged.
Both are destroyed — remember to pop and not push.
Nothing can hit it, so it is pushed directly.
The while loop pops repeatedly, which is why it must be a loop rather than a single if.