Algorithm

Asteroid Collision

Monotonic Stack Pattern

Asteroid Collision

Simulate asteroid collisions where absolute value is size and sign is direction (+ right, - left).

CONSTRAINTS
  • 2 <= asteroids.length <= 10⁴
  • -1000 <= asteroids[i] <= 1000
  • asteroids[i] != 0
EXAMPLE 1
Input: asteroids = [5,10,-5]
Output: [5,10]
10 and -5 collide, 10 wins. 5 and 10 move right.
EXAMPLE 2
Input: asteroids = [10,2,-5]
Output: [10]
2 and -5 collide, -5 wins. Then 10 and -5 collide, 10 wins.
EXAMPLE 3
Input: asteroids = [8,-8]
Output: []
Both moving toward each other with same size. Both are destroyed.
Do asteroids in the same direction collide?
No. They maintain a constant speed and distance. Only asteroids moving toward each other (+) then (-) can collide.
What if there are only negative asteroids?
They all survive. Since they are moving left, and there are no positive asteroids to their left to hit them, they never encounter any obstacles.

Two asteroids can only collide when a right-moving one (positive) sits somewhere to the left of a left-moving one (negative) — they close the gap between them. Two right-movers never catch each other, and two left-movers drift apart forever. So the only interesting moment is a negative asteroid meeting the right-movers ahead of it.

The thing that makes a stack the natural fit is which asteroid a left-mover hits first: the most recently added surviving right-mover — the one nearest to it. And if that collision destroys the right-mover, the left-mover keeps travelling and immediately meets the next most recent survivor, and so on. "Deal with the most recent survivor, and if it's gone, fall back to the one before it" is exactly last-in-first-out, which is what a stack gives you. Keep a stack of everything that has survived so far, in order; each incoming asteroid either passes through quietly or triggers a short chain of collisions off the top.

For each asteroid: if it's moving right, or the stack has nothing to its left that could hit it, it just survives onto the stack. If it's moving left, run it against the right-movers on top:
- top is smaller → the top explodes (pop), and our asteroid keeps going to meet whatever's beneath;
- top is equal in size → both explode;
- top is bigger → our asteroid explodes and the stack is untouched.
Only if it clears every right-mover in its path (stack empties, or the next survivor is itself a left-mover) does it land on the stack as a survivor.

python
def asteroid_collision(asteroids):
    stack = []
    for a in asteroids:
        alive = True
        # only a left-mover meeting a right-mover on top can collide
        while alive and a < 0 and stack and stack[-1] > 0:
            top = stack[-1]
            if top < -a:
                stack.pop()          # top is smaller: it explodes, 'a' travels on
            elif top == -a:
                stack.pop()          # equal size: both explode
                alive = False
            else:
                alive = False        # top is bigger: 'a' explodes
        if alive:
            stack.append(a)
    return stack

Every asteroid is pushed at most once and popped at most once, so the whole chain-reaction simulation runs in one linear pass.

Worked Example:[10, 2, -5]
- 10 → moves right, survives. Stack: [10]
- 2 → moves right, survives. Stack: [10, 2]
- -5 → hits top 2: size 5 > 2, the 2 explodes → [10]. Now hits 10: size 5 < 10, so -5 explodes and 10 stands.
- Result: [10].
Interactive Strategy Visualization
COLLISION PHYSICS INSIGHT

Stack-based multi-collision chain reaction

10
Empty space. 10 (Right) enters the void.

Mental Model

  • Stack as History: The stack tracks asteroids currently flying Right (+). They are the potential targets for incoming Left (-) asteroids.
  • Cascading Collisions: A single incoming (-) asteroid can trigger a chain reaction, destroying multiple (+) asteroids in the stack until it meets its match or survives.
  • Momentum: (-, +) never collide because they are already moving away from each other. (+, -) is the only collision case.
SIMULATION LOGSTEP 1/8
Empty space. 10 (Right) enters the void.
RULES

Interaction Physics

1. Positive (+) flies Right. 2. Negative (-) flies Left. 3. Larger Mass survives. 4. If Equal Mass, both are destroyed. 5. Only Right-Left pairs collide.

O(N²) Re-simulate Until Stable
O(N) Stack Simulation