Asteroid Collision Explained: Tracing [5, 10, -5], [8, -8], & [10, 2, -5]

Imagine an infinite expanse of space where asteroids move along a single track, some drifting to the right with positive velocities and others speeding left with negative velocities. When you are given the initial array sequence like $[5,10,-5]$, you might be tempted to just look at adjacent pairs from left to right. But what happens when an asteroid in the middle is destroyed, causing two distant bodies to suddenly crash into each other that weren't adjacent before?

If we look at our locked working example of [5, 10, -5], the $-5$ is moving left and is about to smash into the $+10$ moving right. But notice how $+10$ survives that clash and keeps its trajectory, leaving a trailing $+5$ behind it. A simple one-pass left-to-right sweep completely misses how a newly exposed right-moving asteroid might interact with elements further back in the sequence.

Without a proper data structure to remember who survived past skirmishes, our simulation quickly devolves into an unmanageable mess of indices and out-of-order checks. We need a systematic way to process these encounters so that every survival and explosion is accounted for in the exact order of physical impact.

When simulating our working example of asteroids like [5, 10, -5], a naive left-to-right scan breaks down because a single left-moving asteroid can cascade backward, destroying multiple right-moving asteroids that came before it. To capture this domino effect accurately, we need a data structure that remembers the most recent survivors first: a stack.

In our model, positive numbers represent asteroids moving right, and negative numbers represent asteroids moving left. As we iterate through the array, any right-moving asteroid ($>0$) is safely pushed onto our stack because it can only collide with something yet to be encountered on its right. However, the moment we encounter a left-moving asteroid ($<0$), it immediately challenges the top of the stack.

Let us map this to the first part of our working example, [5, 10, -5]. The 5 and 10 enter the stack unopposed as right-movers, forming our active baseline. When the $-5$ arrives, it doesn't scan the whole array; it inspects only the top element of the stack (10). Because $-5$ has a smaller absolute value than 10, the $-5$ is destroyed, leaving the stack intact.

Let's apply our stack mental model directly to our three distinct scenarios: $[5,10,-5]$, $[8,-8]$, and $[10,2,-5]$. We will trace how right-movers accumulate on the stack and how incoming left-movers trigger destruction or self-destruction.

Scenario 1: $[5,10,-5]$

- Step 1: Push 5 onto the stack. Stack = $[5]$.
- Step 2: Push 10 onto the stack. Stack = $[5,10]$.
- Step 3: Encounter $-5$ (moving left). It collides with the top of the stack, which is 10 (moving right).
- Step 4: Compare magnitudes: $|-5|=5$ and $|10|=10$. Since $10>5$, the right-mover 10 wins. The incoming $-5$ is destroyed.
- Result: The surviving stack is $[5,10]$.

Scenario 2: $[8,-8]$

- Step 1: Push 8 onto the stack. Stack = $[8]$.
- Step 2: Encounter $-8$ (moving left). It collides with the top of the stack, 8.
- Step 3: Compare magnitudes: $|-8|=8$ and $|8|=8$. They are equal, so both asteroids explode.
- Result: The stack is now empty: $[]$.

Scenario 3: $[10,2,-5]$

- Step 1: Push 10 onto the stack. Stack = $[10]$.
- Step 2: Push 2 onto the stack. Stack = $[10,2]$.
- Step 3: Encounter $-5$ (moving left). It collides with the top of the stack, 2.
- Step 4: Compare magnitudes: $|-5|=5$ and $|2|=2$. The incoming $-5$ wins, destroying 2. Pop 2 off the stack. Stack = $[10]$.
- Step 5: The same $-5$ continues moving left and collides with the new top of the stack, 10.
- Step 6: Compare magnitudes: $|-5|=5$ and $|10|=10$. The right-mover 10 wins. The incoming $-5$ is destroyed.
- Result: The surviving stack is $[10]$.

Try this: Stack trace for [10, 2, -5]:

Final Stack: [10]

You have seen how positive and negative velocities interact using our stack model, resolving right-moving survivors against oncoming left-movers. Now it is time to apply those exact rules to a new sequence. Look at the array of velocities $[10,2,-5]$ from our working example and trace what happens when the left-moving $-5$ encounters the top of the stack.

Remember the three collision outcomes:

Work through the sequence step-by-step on a piece of scratchpad paper before checking your reasoning against the rules established in the previous phases.

The stack behavior we unlocked while resolving [10, 2, -5] is not just about rocks in space—it is a fundamental pattern for sequential annihilation problems. Whenever an incoming stream of events can retroactively destroy past state in a Last-In-First-Out order, a stack is your primary architectural tool. Consider how an incoming left-moving asteroid at $-5$ cascades backward through the stack, destroying the top element 2 and then colliding with 10. This exact same destruction-from-the-top logic governs syntax parsing, temperature spikes, and span-based array problems like daily stock spans.

To see this transfer in action, look at how consecutive matching parentheses or asteroid velocities share the exact same cancellation trigger. When a new element enters, you compare it against the peek of your history. If it wins, you pop the history and repeat the check. If it loses, the incoming element vanishes. If they are equal, both vanish. By abstracting our asteroid collision rules, we see that any domain involving directional opposition and cascading elimination reduces to a single linear pass backed by a stack.

def asteroid_collision(asteroids):
    stack = []
    for ast in asteroids:
        # TODO: Implement collision resolution using the stack model
        pass
    return stack