Asteroid Collision
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.
- 2 <= asteroids.length <= 10⁴
- -1000 <= asteroids[i] <= 1000
- asteroids[i] != 0
Intuition
Asteroid collision simulates asteroids moving along a line, where positive values travel right and negative travel left. A collision destroys the smaller; equal sizes destroy both.
The first thing to pin down is when a collision actually happens. Two asteroids collide only when the left one moves right and the right one moves left — they must be approaching. Every other pairing is safe:
- A collision occurs only between a positive asteroid followed by a negative one; -5 then 5 move apart and never meet.
Getting this backwards is the most common wrong answer, because it looks symmetric but is not.
A right-moving asteroid that survives can still be hit by a later left-moving one, so survivors must be remembered in order — and the most recent survivor is always the first to be tested. Last in, first tested is a stack.
Process asteroids left to right. A right-mover is pushed. A left-mover is compared against the top of the stack while that top is a right-mover:
The stack top is popped when it is smaller, the incoming asteroid is destroyed when it is smaller, and both are destroyed when sizes are equal. That third case is easy to omit and produces a surviving asteroid that should not exist.
A left-mover surviving the whole loop — including the case of an empty stack — is pushed, since nothing to its left can ever reach it. The stack read bottom to top is the final state, already in order.
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
Before reading on: price up what the direct approach costs here, then ask what unresolved thing you are holding, and what event finally resolves it. Aim for O(n) time and O(n) space.
Identify when a collision happens
Only a positive asteroid followed by a negative one collides — they are approaching. -5 then 5 move apart and never meet, and reversing this is the usual source of wrong answers.
Use a stack for survivors
A surviving right-mover can still be hit by a later left-mover, and the most recent survivor is always tested first. Last in, first tested is exactly a stack.
Push right-moving asteroids
A positive asteroid cannot collide with anything already processed, since everything to its left that survived is also moving right. Push it and move on.
Resolve a left-mover against the stack
While the top is a right-mover, compare sizes: pop the top when it is smaller, and stop when the incoming asteroid is smaller — it is destroyed.
Destroy both when sizes are equal
Equal sizes destroy both — pop the top and stop processing the incoming asteroid. Omitting this case leaves a survivor that should not exist.
Push a surviving left-mover
If the stack empties or its top is already a left-mover, the incoming asteroid survives permanently — nothing further left can reach it. Push it.
Cost of the simulation
Each asteroid is pushed and popped at most once, giving O(n) time and O(n) space. The stack read bottom to top is the answer, already in the correct order.
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.