Asteroid Collision Problem Using Stacks

Asteroids move in a row. Each asteroid has a size and direction: positive means moving right, negative means moving left. When two asteroids meet, the smaller one explodes. If they’re the same size, both explode. Asteroids moving in the same direction never meet.

When Do Collisions Happen?

A collision only occurs when a right-moving asteroid (positive) is followed by a left-moving asteroid (negative). Two left-moving or two right-moving asteroids never collide.

[5, 10, -5]  → [5, 10]     (10 destroys -5)
[8, -8]      → []           (mutual destruction)
[-2, -1, 1, 2] → [-2,-1,1,2] (no collision, moving apart)

Solution

def asteroid_collision(asteroids):
    """
    Simulate asteroid collisions.
    Time: O(n), Space: O(n)
    """
    stack = []

    for asteroid in asteroids:
        alive = True

        while alive and stack and asteroid < 0 < stack[-1]:
            # Collision: right-moving (stack top) vs left-moving (current)
            if stack[-1] < -asteroid:
                stack.pop()  # Stack top is smaller, it explodes
            elif stack[-1] == -asteroid:
                stack.pop()  # Same size, both explode
                alive = False
            else:
                alive = False  # Current asteroid is smaller, it explodes

        if alive:
            stack.append(asteroid)

    return stack

Trace

Input: [5, 10, -5]

asteroid | stack      | action
---------|------------|-------
5        | [5]        | push (moving right)
10       | [5, 10]    | push (moving right)
-5       | [5, 10]    | collision: |10| > |-5| → -5 explodes

Output: [5, 10]

Input: [10, 2, -5]

asteroid | stack      | action
---------|------------|-------
10       | [10]       | push
2        | [10, 2]    | push
-5       | [10, 2]    | collision: |2| < |-5| → 2 explodes
         | [10]       | collision: |10| > |-5| → -5 explodes

Output: [10]

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

asteroid | stack          | action
---------|----------------|-------
-2       | [-2]           | push (moving left, no collision)
-1       | [-2, -1]       | push (both moving left)
1        | [-2, -1, 1]    | push (top is negative, no collision)
2        | [-2, -1, 1, 2] | push (both moving right)

Output: [-2, -1, 1, 2]

Why a Stack?

The stack naturally models “what’s still alive.” Each new asteroid only interacts with the most recent right-moving asteroid (the stack top). If the new asteroid destroys it, it then faces the next one — exactly how pop works.

Edge Cases

• All moving same direction — no collisions, return as-is
• All moving left then all right — [-3,-2,1,2] → no collisions
• Chain destruction — [1,2,3,-10] → [-10] (the -10 destroys everything)
• Mutual destruction chain — [1,-1,2,-2] → []
• Empty array — return []

Complexity

Each asteroid is pushed at most once and popped at most once: O(n) time, O(n) space.

When to Use This Pattern

Anytime you have elements that interact with their neighbors in a “last one wins” pattern:

• Bracket matching
• Stock prices with thresholds
• Particle collision simulations

Related Problems

• Daily Temperatures (LeetCode 739) — stack for nearest greater
• Remove K Digits (LeetCode 402) — stack with removal logic
• Online Stock Span (LeetCode 901) — stack for spanning