Asteroid Collision: Stack Simulation

LeetCode 735: Asteroid Collision is one of those problems that sounds like a physics simulation but is really a stack exercise in disguise. You have asteroids flying in two directions, and when they collide, the smaller one explodes. The tricky part is handling the chain reactions: one collision can expose the next asteroid to yet another collision. A stack makes this clean and efficient.

The problem

You are given an array of integers representing asteroids in a row. For each asteroid, the absolute value represents its size and the sign represents its direction: positive means moving right, negative means moving left. Asteroids moving in the same direction will never meet. When two asteroids moving in opposite directions meet, the smaller one explodes. If they are the same size, both explode. Find the state of the asteroids after all collisions.

Input:  [5, 10, -5]
Output: [5, 10]

Input:  [8, -8]
Output: []

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

The approach

The key insight is that collisions only happen when a right-moving asteroid (positive) is followed by a left-moving asteroid (negative). Two asteroids moving in the same direction never collide, and a left-moving asteroid followed by a right-moving one will fly apart forever.

A stack is the perfect data structure here because each new asteroid only needs to interact with the most recently added ones. Here is the approach:

1. Iterate through each asteroid in the array from left to right.
2. For each asteroid, check if it would collide with the top of the stack. A collision happens when the current asteroid is negative (moving left) and the top of the stack is positive (moving right).
3. If they collide, compare their sizes. The smaller one is destroyed. If they are equal, both are destroyed. If the current asteroid survives, it may collide with the next element on the stack, so keep checking.
4. If no collision occurs (or the current asteroid survives all collisions), push it onto the stack.

def asteroid_collision(asteroids: list[int]) -> list[int]:
    stack = []
    for ast in asteroids:
        alive = True
        while alive and stack and ast < 0 < stack[-1]:
            if stack[-1] < -ast:
                stack.pop()
            elif stack[-1] == -ast:
                stack.pop()
                alive = False
            else:
                alive = False
        if alive:
            stack.append(ast)
    return stack

Step-by-step walkthrough

Let's trace through the input [5, 10, -5] to see how the stack processes each asteroid and handles the collision.

The walkthrough shows the core mechanic: the while loop only activates when a left-moving asteroid meets a right-moving one on the stack. In this case, the -5 loses to the 10 and is destroyed immediately. In more complex inputs, a single left-moving asteroid can destroy multiple right-moving ones before being stopped.

Complexity analysis

Time: Each asteroid is pushed onto the stack at most once and popped at most once. Even though the inner while loop can pop multiple elements for a single asteroid, the total number of pops across the entire algorithm cannot exceed n. This gives O(n) total work.

Space: In the worst case, no collisions occur (for example, all asteroids move in the same direction), and the stack holds all n elements. So the space is O(n).

The building blocks

Stack as collision simulator

This problem demonstrates a powerful stack pattern: using the stack to simulate interactions between elements where the current element can "cancel out" previous ones. You scan left to right, and the stack holds everything that has survived so far. Each new element either coexists peacefully with the stack or triggers a chain of destructions.

The while loop is what makes this work. A simple if statement would only handle one collision, but asteroids can chain. Consider [5, 3, 2, -10]: the -10 needs to destroy the 2, then the 3, then the 5. The while loop keeps popping until either the current asteroid is destroyed, the stack is empty, or the top of the stack moves in the same direction.

This pattern appears in other problems too. Any time you need to process a sequence where new elements can invalidate or cancel previous elements, a stack with a while-loop check is the go-to approach. The "alive" flag is a clean way to track whether the current element survives the collision loop, and it avoids messy break/continue logic.

Edge cases

All asteroids move in the same direction like [1, 2, 3] or [-3, -2, -1]: no collisions happen at all. Every asteroid gets pushed onto the stack, and the output equals the input.

Equal-size collision like [8, -8]: both asteroids are destroyed. The result is an empty array. Make sure your code handles the case where stack[-1] == -ast by both popping the stack and marking the current asteroid as not alive.

Chain reaction like [10, 2, -5]: the -5 first destroys the 2, then collides with the 10. Since 10 is larger, the -5 is destroyed too. The while loop handles this naturally by continuing to check the stack after each pop.

Left-moving asteroids come first like [-2, -1, 1, 2]: left-moving asteroids at the start of the array can never collide with anything because there is nothing to their right moving toward them. They pass through to the result unchanged.

From understanding to recall

The asteroid collision problem has a deceptively simple core: scan left to right, use a stack, pop on collision. But the details matter. You need to remember the three-way comparison (current is bigger, equal, or smaller), the alive flag, and the exact while-loop condition ast < 0 < stack[-1]. These are the pieces that trip people up under interview pressure.

Spaced repetition turns this from "I vaguely remember a stack problem with asteroids" into "I can write the collision loop cold in two minutes." Each time you practice, the condition check and the alive-flag pattern get more automatic. After a few repetitions, you will not need to think about whether to use < or > in the comparison. It will just be there.

Related posts

• Daily Temperatures - Another monotonic stack problem
• Evaluate Reverse Polish Notation - Stack-based expression evaluation
• Valid Parentheses - Classic stack matching problem

CodeBricks breaks the stack simulation pattern into its reusable pieces and drills them individually. You practice the collision loop from scratch each time, building the muscle memory so that when you see Asteroid Collision or similar stack simulation problems in an interview, the code flows without hesitation.