Community Problem
Asteroid Collision
Difficulty: Medium
Simulate collisions between right- and left-moving asteroids using a stack of survivors, popping while the top loses head-on encounters.
Asteroid Collision
Simulate collisions between right- and left-moving asteroids using a stack of survivors, popping while the top loses head-on encounters.
By @jamalvargas
December 2, 2025
·
Updated May 18, 2026
1,159 views
20
4.4 (11)
Got asked this on an L5 Google interview loop, and the gotcha was the equal-mass case: the candidate before me had spent 25 minutes debugging an inner loop that double-popped when both asteroids should annihilate. The clean version is a tight stack with one outer for-loop and one inner while-loop.
Asteroid Collision
You are given an integer array asteroids where each non-zero entry represents an asteroid in space. The absolute value is the asteroid's mass; the sign indicates direction (positive moves right, negative moves left). All asteroids start in a row and move at the same speed. When two asteroids collide head-on (a right-mover meets a left-mover), the smaller one (by absolute value) explodes. If they have equal absolute value, both explode. Asteroids moving in the same direction never collide.
Return the state of the asteroids after all collisions resolve.
Examples
Example 1:
- Input:
asteroids = [5, 10, -5] - Output:
[5, 10] - Explanation:
10and-5collide;10is bigger and survives.5and10move in the same direction.
Example 2:
- Input:
asteroids = [8, -8] - Output:
[] - Explanation: Equal mass, both explode.
Example 3:
- Input:
asteroids = [10, 2, -5] - Output:
[10] - Explanation:
2and-5collide,2explodes. Then10and-5collide,-5explodes.
Example 4:
- Input:
asteroids = [-2, -1, 1, 2] - Output:
[-2, -1, 1, 2] - Explanation: Left-movers stay on the left, right-movers stay on the right; no head-on collisions occur.
Constraints
2 <= asteroids.length <= 10^4-1000 <= asteroids[i] <= 1000asteroids[i] != 0
Solution
Hints
Approach
A stack of survivors that we update as we scan left to right captures the dynamics exactly. Two asteroids a and b collide head-on if and only if a > 0 (right-moving) is BEFORE b < 0 (left-moving) in the order, and there is no surviving right-mover between them. So whenever the next asteroid is negative and the current top of the stack is positive, we have a pending collision to resolve.
Key insight
A negative incoming asteroid keeps eating positive tops one at a time, popping any whose absolute value is strictly less. The cascade stops at one of three outcomes: the stack becomes empty or its top is also negative (incoming survives, push it), the top equals the incoming in magnitude (both die, pop top, drop incoming), or the top has strictly larger magnitude (incoming dies, top stays).
Algorithm
- Initialize an empty stack.
- For each asteroid
ain input order, setalive = true. WhilealiveANDa < 0AND the stack is non-empty ANDstack.top > 0:- If
stack.top < -a: pop (smaller right-mover destroyed, current keeps cascading). - Else if
stack.top == -a: pop and setalive = false(both annihilate). - Else: set
alive = false(current is destroyed).
- If
alive, pusha. - Return the stack as an array.
Complexity
Metric Value
------ -----
Time O(n) amortized
Space O(n) for the stack of survivorsEach asteroid is pushed at most once and popped at most once, so the inner while loop's total work across the whole scan is O(n).
Why it works
A collision can only occur between a right-mover that is to the LEFT of a left-mover, with no surviving right-mover between them. The stack maintains exactly the surviving right-moving suffix (followed possibly by left-movers that escaped to the left). When a new left-mover arrives, the only candidates it could collide with are at the top of that suffix, in last-in-first-out order, which is exactly the stack invariant.
Pitfalls
- Equal-mass case: easy to forget to set
alive = falseAFTER popping, which leaves the current asteroid alive and lets it incorrectly destroy more. - The collision predicate is
a < 0 AND stack.top > 0. Both conditions are required. Two same-sign asteroids never collide. - Using
stack[stack.length - 1]after popping inside the loop without re-reading. Re-readtopat the start of every iteration. - Be careful with magnitude comparisons. The cleanest invariant is
top < -afor "top is destroyed and current survives".
Solution Code