Asteroid Collision
Simulate asteroid collisions with a stack of survivors: only a left-mover meeting a right-mover on top can collide, and the smaller one explodes.
Problem Understanding
Asteroid Collision: each integer is an asteroid in a row. Its absolute value is its size and its sign is its direction: positive moves right, negative moves left, all at the same speed. When two meet, the smaller explodes; equal sizes both explode. Return the asteroids left after all collisions.
Example: [5, 10, -5] returns [5, 10]: -5 meets 10 and explodes.
The Intuition: Survivors on a Stack
Process asteroids left to right and keep the survivors on a stack. A new asteroid can only collide if it moves left and the top survivor moves right; every other pair never meets.
When they do collide, compare sizes:
- Top is smaller: it explodes. Pop it, and the incoming asteroid keeps flying into the next top.
- Same size: pop the top; the incoming one is gone too.
- Top is bigger: the incoming one explodes; the stack is unchanged.
If the incoming asteroid is still alive, push it. The same "pop while the top loses" loop drives Daily Temperatures and Car Fleet.
Interactive Walkthrough
The asteroids are on top, with an arrow under each for its direction; below them, the survivors on the stack. When something explodes it turns red for one step. Try the Chain preset to watch one big left-mover clear three asteroids in a row.
Dry Run Table
Input: [10, 2, -5]
| Incoming | Top | Outcome | Stack after |
|---|---|---|---|
| 10 | — | push | [10] |
| 2 | 10 | same direction, push | [10, 2] |
| -5 | 2 | 2 < 5: 2 explodes | [10] |
| -5 | 10 | 10 > 5: -5 explodes | [10] |
Answer: [10].
The Solution Template
A stack of survivors and an alive flag for the incoming asteroid.
Asteroid Collision Code
1var asteroidCollision = function(asteroids) {2 const stack = [];3 for (const a of asteroids) {4 let alive = true;5 while (alive && a < 0 && stack.length && stack[stack.length - 1] > 0) {6 const top = stack[stack.length - 1];7 if (top < -a) {8 stack.pop();9 continue;10 }11 if (top === -a) stack.pop();12 alive = false;13 }14 if (alive) stack.push(a);15 }16 return stack;17};
Edge Cases & Common Mistakes
- Left-mover first, right-mover after (
[-2, 2]): they move apart and never collide. Checka < 0andtop > 0, not just opposite signs. - Equal sizes: both explode; pop the top and drop the incoming one.
- Chain reactions: one large left-mover can clear many tops; the
whileloop keeps going after each smaller top explodes. - Everything explodes: the answer can be empty, e.g.
[8, -8]. - Java output:
ArrayDequepops from the top, so fill the result array from the back to keep left-to-right order.
Summary
Keep survivors on a stack. Only a negative incoming asteroid can hit a positive top: smaller tops explode and the loop continues, an equal top takes both out, a bigger top destroys the incoming one. Push whatever survives. O(n) time, O(n) space.
More practice: DSA interview questions with answers · patterns cheat sheet