Asteroid Collision (LeetCode 735)

The problem

You get an array of non-zero integers, each an asteroid in a row. The absolute value is its size; the sign is its direction (positive moves right, negative moves left). All move at the same speed. When two meet, the smaller one explodes; if they are the same size, both explode. Asteroids moving the same way never meet. Return the asteroids left after all collisions, in order.

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

-5 meets 2 first and destroys it, then meets 10 and is destroyed itself.

How to think about it

Start with brute force. Simulate in rounds: scan for any adjacent pair (+, -), resolve it, rebuild the array, and repeat until no such pair is left. Each round is O(n) and you can need O(n) rounds, so that is O(n²).

When does a collision actually happen? Only when a right-mover is to the left of a left-mover: + then -. A left-mover with nothing but left-movers before it flies away safely. A right-mover followed by more right-movers is safe too, for now. So the only interesting moment is when you read a negative asteroid while the previous survivor is positive.

The key insight: keep the survivors so far on a stack. Process asteroids left to right. A new left-mover only fights the survivor nearest to it, which is the top of the stack. If it wins, that survivor is gone and it fights the next one down. This repeats until it dies, ties, or there are no right-movers left on top. Each asteroid is pushed once and popped at most once.

Which pattern is this? A stack simulation, close cousin of the monotonic stack: each new element pops from the top while some condition holds. The tell is “a new item interacts only with the most recent survivor, and may wipe out several in a row”.

Approach

1. Create an empty stack st of survivors.
2. For each asteroid a, set alive = True. While alive, a < 0, and the top of st is positive:
   • If the top is smaller than |a|, pop it and keep fighting.
   • If the top equals |a|, pop it and set alive = False (both explode).
   • Otherwise the top is bigger, so alive = False.
3. If a is still alive, push it.
4. Return st.

Solution

def asteroid_collision(asteroids):
    st = []
    for a in asteroids:
        alive = True
        while alive and a < 0 and st and st[-1] > 0:   # only + then - collide
            if st[-1] < -a: st.pop()                    # top explodes, keep going
            elif st[-1] == -a: st.pop(); alive = False  # both explode
            else: alive = False                         # a explodes
        if alive:
            st.append(a)
    return st
# asteroid_collision([5,10,-5]) -> [5,10]
# asteroid_collision([8,-8])    -> []
# asteroid_collision([10,2,-5]) -> [10]

Dry run

On [10, 2, -5]:

On [5, 10, -5] the -5 ties with nothing and simply loses to 10, leaving [5, 10].

Complexity

• Time: O(n). Each asteroid is pushed at most once and popped at most once, so the inner loop does O(n) work in total.
• Space: O(n). If no collisions happen, every asteroid ends up on the stack.

Edge cases and pitfalls

• - then + never collide: [-2, 3] returns [-2, 3]. Only check collisions when the new asteroid is negative and the top is positive.
• Equal sizes: both explode. Forgetting to set alive = False after the pop would wrongly push the left-mover.
• A chain of wins: [1, 2, 3, -10] must pop all three and then push -10. A single if instead of a while gets this wrong.
• Everything destroyed: [8, -8] returns [].

Related problems

• Remove K Digits (LeetCode 402): each new digit may pop several larger ones from the top.
• Evaluate Reverse Polish Notation (LeetCode 150): another stack where new tokens combine with the top.
• Backspace String Compare (LeetCode 844): a # “destroys” the previous character, a simpler version of the same stack idea.