Asteroid Collision — Stack Simulation for Directional Collisions

Problem Statement#

We are given an array asteroids of integers representing asteroids in a row. For each asteroid, the absolute value represents its size and the sign represents its direction (positive = right, negative = left). Each asteroid moves at the same speed.

Find the state of the asteroids after all collisions. If two asteroids meet, the smaller one explodes. If both are the same size, both explode. Two asteroids moving in the same direction will never meet.

Constraints:

• 2 <= asteroids.length <= 10^4
• -1000 <= asteroids[i] <= 1000
• asteroids[i] != 0

Input:  asteroids = [5,10,-5]
Output: [5,10]
Explanation: 10 and -5 collide → 10 wins. 5 and 10 never collide (same direction).

Input:  asteroids = [8,-8]
Output: []
Explanation: 8 and -8 collide and both explode.

Input:  asteroids = [10,2,-5]
Output: [10]
Explanation: 2 and -5 collide → -5 wins. Then 10 and -5 collide → 10 wins.

Why This Problem Matters#

LC 735 is a classic stack collision simulation problem asked at Amazon, Bloomberg, and Facebook. It tests the ability to identify when a stack is the right structure for a simulation problem involving pending collisions.

The key insight: right-moving asteroids accumulate as "pending" — they may collide with future left-moving asteroids. A stack naturally stores these pending right-movers. When a left-moving asteroid arrives, it destroys right-movers until either it is destroyed itself or no right-moving asteroids remain.

This pattern — pushing elements that may interact with future elements, and popping on interaction — is the same pattern in Valid Parentheses (bracket matching), Asteroid Collision (size comparison), and more complex variants like collision modeling in physics simulations.

The Core Insight#

When does a collision happen? Only when a left-moving asteroid (negative) encounters a right-moving asteroid (positive) that was pushed to the stack earlier. Same-direction asteroids never collide.

Stack invariant: The stack always contains asteroids in a "stable" configuration — no two adjacent asteroids in the stack would collide with each other. All positive (right-moving) asteroids stay on the stack until a negative (left-moving) asteroid destroys them.

Processing each asteroid a:

1. If a > 0 (right-moving): always push — it cannot collide with what is already on the stack (stack contains only stable configurations, and right-movers never collide with past asteroids).
2. If a < 0 (left-moving): potentially collides with the top of the stack if the top is positive:
   • Stack top is smaller (stack[-1] < -a): stack top explodes (pop), asteroid a survives, continue loop.
   • Stack top is equal (stack[-1] == -a): both explode (pop, and a is destroyed).
   • Stack top is larger (stack[-1] > -a): a explodes, stop.
   • Stack is empty or stack top is also negative: no collision, push a.

Visual Dry Run#

Input: [10, 2, -5]

Result: [10] ✓

Input: [8, -8]

Result: [] ✓

Input: [-2, -1, 1, 2]

Result: [-2,-1,1,2] — no collisions because the negatives are moving left (away from positives).

Solution (Optimal)#

# Python — stack collision simulation, O(n) time and space
def asteroidCollision(asteroids: list[int]) -> list[int]:
    stack = []  # stores surviving asteroids in stable configuration
 
    for a in asteroids:
        alive = True  # tracks whether asteroid 'a' survives
 
        # Collision happens when 'a' is left-moving and top of stack is right-moving
        while alive and a < 0 and stack and stack[-1] > 0:
            top = stack[-1]
            if top < -a:
                # Right-moving asteroid is smaller → it explodes, 'a' continues
                stack.pop()
            elif top == -a:
                # Equal size → both explode
                stack.pop()
                alive = False
            else:
                # Right-moving asteroid is larger → 'a' explodes
                alive = False
 
        if alive:
            stack.append(a)
 
    return stack

// JavaScript — stack collision simulation, O(n) time and space
function asteroidCollision(asteroids) {
    const stack = [];
 
    for (const a of asteroids) {
        let alive = true;
 
        while (alive && a < 0 && stack.length > 0 && stack[stack.length - 1] > 0) {
            const top = stack[stack.length - 1];
            if (top < -a) {
                stack.pop();  // right-moving smaller → explodes, a continues
            } else if (top === -a) {
                stack.pop();  // equal → both explode
                alive = false;
            } else {
                alive = false;  // right-moving larger → a explodes
            }
        }
 
        if (alive) {
            stack.push(a);
        }
    }
 
    return stack;
}

Complexity:

Common Mistakes#

1. Forgetting the alive flag. After an equal-size collision, asteroid a is destroyed (not pushed). Without the alive flag, you might push a destroyed asteroid or loop incorrectly.

2. Not handling the case where the stack top is also negative. If the stack top is negative and a is also negative, there is no collision — both are moving left. The condition stack[-1] > 0 correctly ensures we only collide with right-moving asteroids.

3. Forgetting that multiple collisions can cascade. A single left-moving asteroid may destroy multiple right-moving asteroids before being destroyed itself (or surviving). The while loop handles this cascade.

4. Using abs(a) instead of -a for size comparison. Since a is guaranteed negative in the collision check, -a is its absolute size. Both abs(a) and -a work, but -a is slightly faster.

5. Returning stack as-is in Java without converting. Java's Deque iterates in LIFO order. Convert to array properly — either push to a list and convert, or use an ArrayDeque and collect in insertion order.

Interview Tips#

• Name the invariant: "The stack always holds a stable configuration — no two adjacent asteroids in the stack would collide. The while loop restores this invariant after each new asteroid."
• Trace through the [10, 2, -5] example step by step — it shows the cascading collision.
• Handle the equal-size case explicitly: "When sizes are equal, both explode — set alive = False and pop the stack top."
• Mention the amortized O(n) argument: "Each asteroid is pushed once and popped at most once → at most 2n operations total."

Follow-up Questions#

1. What if asteroids can also move at different speeds? Two right-movers at different speeds will eventually collide. Model with time of collision calculations — much harder.
2. What if there is a wall at each end that reflects asteroids? Surviving asteroids that hit a wall change direction — extend the simulation with reflection rules.
3. What if the size comparison used >= instead of >? The equal-size collision rule changes — a larger left-mover now also survives equal collisions.
4. Count total asteroids destroyed. Track a counter incremented each time stack.pop() is called, and also when alive = False without a pop (the incoming asteroid is destroyed).
5. Return both survivors and the number of collisions. Track a collision counter alongside the stack.

Key Takeaways#

• A stack models the "pending right-movers waiting for future left-movers" perfectly — LIFO matches the collision order (most recent right-mover collides first).
• The collision condition is: a < 0 (left-moving) AND stack[-1] > 0 (top is right-moving). Any other combination has no collision.
• Three collision outcomes: right-mover explodes (pop, a continues), both explode (pop, alive = False), left-mover explodes (alive = False without pop).
• Use an alive flag to track whether the current asteroid survives the cascade of collisions before being pushed.
• Each asteroid is pushed at most once and popped at most once → O(n) amortized time.
• This pattern — pushing pending elements and popping on conflict — is the same as Valid Parentheses, stock span, and monotonic stack problems.