Asteroid Collision Solution

Problem

You have a row of asteroids traveling in a line. Each asteroid's absolute value is its size, and the sign tells you its direction: positive means right, negative means left. All asteroids move at the same speed, and two asteroids only collide when one is heading right and another is heading left directly behind it. The smaller asteroid explodes; if they're the same size, both explode.

Input: asteroids = [10, 2, -5]
Output: [10]
Explanation: 2 and -5 collide first — 2 explodes. Then 10 and -5 collide — -5 explodes.

A trickier case: [8, -8] → [] — both asteroids are equal, so both explode.

Intuition

The key insight is that a collision can only happen at the boundary between a rightward asteroid and a leftward one coming up behind it. A stack naturally models this: push rightward asteroids as candidates, and when a leftward asteroid arrives, repeatedly check the top to see which survives. Once the leftward asteroid either explodes or clears all rightward candidates, it either joins the stack or disappears.

Solution — Stack Simulation

Iterate through each asteroid. Positive ones are pushed immediately — they can only collide with future leftward asteroids. For each negative asteroid, keep checking the stack top as long as there's a rightward candidate there: pop the top if it's smaller, stop if it's larger, or pop the top and destroy both if they're equal.

Initialize an empty stack.
For each asteroid, set a flag indicating it is still alive.
While alive, the asteroid is negative, the stack is non-empty, and the stack top is positive — a collision occurs:
- Top smaller: pop the top (it explodes), continue checking.
- Equal size: pop the top and mark current as destroyed, stop.
- Top larger: mark current as destroyed, stop.
If the asteroid survived, push it onto the stack.
Return the stack as the result.

1def asteroidCollision(asteroids: list[int]) -> list[int]:
2    stack = []
3    for asteroid in asteroids:
4        alive = True
5        while alive and asteroid < 0 and stack and stack[-1] > 0:
6            if stack[-1] < -asteroid:
7                stack.pop()          # top is smaller, it explodes; keep checking
8            elif stack[-1] == -asteroid:
9                stack.pop()          # equal size, both explode
10                alive = False
11            else:
12                alive = False        # top is larger, current explodes
13        if alive:
14            stack.append(asteroid)
15    return stack

Time: O(n) — each asteroid is pushed and popped at most once, so the total work is linear even with the inner loop.

Space: O(n) — the stack holds at most all n asteroids in the no-collision case.

Complexity Summary

Approach	Time	Space	When to use
Stack Simulation	O(n)	O(n)	Always — this is the canonical solution for this problem

Common Mistakes

Thinking same-direction asteroids collide — only a rightward (+) and a leftward (-) pair can collide; two positives or two negatives traveling together never interact.
Not handling the equal-size case — when stack[-1] == -asteroid, both must be destroyed; a common bug is popping the top but forgetting to mark the current asteroid as dead.
Not looping after one explosion — a single leftward asteroid can destroy multiple rightward ones in sequence; breaking after the first pop produces wrong results like [10, 2, -5] → [10, 2] instead of [10].
Mixing up < and <= in the size check — using stack[-1] <= -asteroid to detect a pop would incorrectly destroy the top when they're equal without also destroying the current asteroid.
Forgetting that a leftward asteroid can survive an empty stack — if no rightward asteroid remains to collide with, the leftward one simply joins the stack; skipping the if alive push drops it.

Asteroid Collision — Solution

Problem

Intuition

Solution — Stack Simulation

Complexity Summary

Common Mistakes

Related Problems

Ready to practice? Try it on SkillFlow