Asteroid Collision

Asteroids move left or right, encoded as sign: positive moves right, negative moves left. All move at the same speed, so two asteroids collide only when one moves right while the other moves left — and then the bigger size survives (equal sizes destroy both).

The key insight: a stack models the line of flight perfectly. The machine processes asteroids left to right; an incoming leftward asteroid collides with the rightward survivor on top of the stack, possibly repeatedly. Each collision resolves one of three ways: the survivor wins and the incoming dies, the incoming wins and the stack pops (then the next comparison runs), or both die. Incoming rightward asteroids never collide with anything currently on the stack.

Approach in steps:

1. For each asteroid, while the stack top is positive and the incoming is negative, resolve the collision.
2. Pop when the incoming is bigger; skip when equal; push when the incoming survives.
3. Return the stack.

def asteroidCollision(asteroids):
    stack = []
    for a in asteroids:
        while stack and stack[-1] > 0 and a < 0:
            if stack[-1] < -a:
                stack.pop()
                continue
            elif stack[-1] == -a:
                stack.pop()
            break
        else:
            stack.append(a)
    return stack

Time is O(n) — each asteroid enters and leaves at most once; space O(n).

Trickiest edge case: a chain of collisions. [10,2,-5] — the incoming -5 kills 2, then meets 10 and dies; the machine must keep looping until the stack top no longer collides. The while-with-continue shape handles that; a single if would stop after the first kill. Equal sizes ([8,-8]) leave an empty result — nothing survives.