Asteroid Collision LeetCode: Stack Simulation Walkthrough

Asteroid Collision (#735) is one of those rare LeetCode problems that is genuinely fun to solve. You are given an array of integers representing asteroids in a row — positive means moving right, negative means moving left. When two asteroids moving in opposite directions meet, the smaller one explodes. If they are the same size, both explode. Your job is to find the state of the asteroids after all collisions.

If you have solved Valid Parentheses or any bracket-matching problem, you already have the core intuition for this one. The asteroid collision leetcode problem uses the exact same push/pop pattern — you maintain a stack, push elements that are "safe," and pop when a conflict arises. The twist is that instead of matching brackets, you are resolving collisions based on size.

This problem is rated Medium on LeetCode and appears frequently in interviews at companies like Amazon, Google, and Microsoft. It tests whether you can adapt the stack pattern beyond simple matching into a simulation with multiple conditional outcomes.

The rules are simple but precise. Each asteroid has a size (absolute value) and a direction (sign). Positive integers move right. Negative integers move left. Two asteroids moving in the same direction will never collide — a right-moving asteroid will never catch another right-moving asteroid ahead of it, and two left-moving asteroids are already heading the same way.

Collisions only happen when a right-moving asteroid (positive) is followed by a left-moving asteroid (negative). When they meet, the larger one survives and the smaller one explodes. If they are the same absolute size, both explode. The surviving asteroids continue moving in their original direction, potentially causing further collisions.

Think of it like a conveyor belt. Asteroids moving right sit on the belt peacefully until a left-moving asteroid comes along and smashes into them from the other direction. The left-moving asteroid keeps destroying right-moving ones until it either explodes itself, finds a bigger one, or clears them all.

The stack is the perfect data structure here because collisions always happen between the most recently added right-moving asteroid and the incoming left-moving asteroid. This is exactly the last-in-first-out behavior that stacks provide. You process asteroids one by one and use the stack to track the ones that are still "alive."

Here is the algorithm. Iterate through each asteroid. If it is positive (moving right), push it onto the stack — it cannot collide with anything already on the stack. If it is negative (moving left), you need to resolve collisions. While the stack top is positive and smaller than the absolute value of the incoming asteroid, pop it — that right-moving asteroid explodes. If the stack top is positive and equal in size, pop it and skip the incoming asteroid — both explode. If the stack top is negative or the stack is empty, push the incoming asteroid — no collision possible.

The key insight is that a negative asteroid only collides with positive ones on the stack. Two negative asteroids on the stack are both moving left and will never interact. This is what makes the asteroid collision stack approach so elegant — you only need to check one condition for collision.

The implementation follows the algorithm directly. Create an empty stack (an array works). For each asteroid in the input, check whether it causes collisions. The while loop handles the chain of collisions a single left-moving asteroid can cause as it plows through smaller right-moving ones.

In Python, the solution looks like this. Initialize an empty list as your stack. For each asteroid, set a boolean flag called "alive" to true. While the asteroid is negative, alive, the stack is not empty, and the stack top is positive: if the stack top is less than the absolute value of the asteroid, pop (it explodes). If they are equal, pop and set alive to false (both explode). If the stack top is larger, set alive to false (incoming explodes). After the while loop, if alive is still true, push the asteroid.

The time complexity is O(n) where n is the number of asteroids. Each asteroid is pushed onto the stack at most once and popped at most once, giving a total of at most 2n operations. The space complexity is O(n) for the stack in the worst case where no collisions occur.

Let us trace through the classic examples to see the leetcode 735 solution in action. For the input [5, 10, -5]: process 5 (positive, push) — stack is [5]. Process 10 (positive, push) — stack is [5, 10]. Process -5 (negative, collide with 10). Since |−5| < 10, the -5 asteroid explodes. Stack remains [5, 10]. Final answer: [5, 10].

For [8, -8]: process 8 (positive, push) — stack is [8]. Process -8 (negative, collide with 8). Since |−8| equals 8, both explode. Pop 8, do not push -8. Stack is empty []. Final answer: [].

For [-2, -1, 1, 2]: process -2 (negative, stack empty, push) — stack is [-2]. Process -1 (negative, stack top is negative, push) — stack is [-2, -1]. Process 1 (positive, push) — stack is [-2, -1, 1]. Process 2 (positive, push) — stack is [-2, -1, 1, 2]. No collisions at all because the negative asteroids are all to the left of the positive ones. Final answer: [-2, -1, 1, 2].

For a harder example, [10, 2, -5]: process 10 (push) — [10]. Process 2 (push) — [10, 2]. Process -5 (collide with 2, |−5| > 2, pop 2). Now collide with 10. Since |−5| < 10, the -5 explodes. Stack is [10]. Final answer: [10]. Notice how -5 destroyed 2 but then lost to 10 — the chain of collisions is why we need a while loop, not just an if statement.

The edge cases in this stack collision problem are what separate a correct solution from one that passes most tests but fails on tricky inputs. The first edge case is all same direction — if every asteroid is positive or every asteroid is negative, no collisions happen and you return the input unchanged. Your code should handle this naturally since the while loop condition will never trigger.

The second edge case is total annihilation — all asteroids destroy each other, leaving an empty array. This happens with inputs like [1, -1] or [3, 5, -5, -3]. Make sure your code handles an empty stack correctly after all processing.

Single asteroid inputs should return the input as-is. Alternating sizes where a large negative asteroid destroys multiple smaller positives in a chain (like [1, 2, 3, -10]) test that your while loop keeps running until the collision chain resolves. Finally, inputs where the negative asteroid is at the very beginning (like [-5, 1, 2]) should push the negative directly since there is nothing to collide with.

Asteroid Collision is a perfect example of stack simulation with conditional push and pop. Unlike Valid Parentheses where every open bracket gets pushed and every close bracket triggers exactly one pop, this problem requires a while loop for chain reactions and three distinct outcomes per collision — incoming wins, stack top wins, or both are destroyed.

The deeper lesson is that stacks are not just for matching pairs. Any time you need to process a sequence where new elements interact with the most recent previous elements, a stack is likely the right tool. Problems like Daily Temperatures, Next Greater Element, and Decode String all use this same intuition of "process the current element against the stack top."

If you found this walkthrough helpful, add Asteroid Collision to your YeetCode flashcard rotation. The stack simulation pattern appears across dozens of LeetCode problems, and the more you practice resolving collisions and chain reactions with a stack, the faster you will recognize the pattern in new problems during interviews.