Asteroid Collision

Apply the collision rule directly to the array, over and over. Sweep left to right; whenever two adjacent asteroids form a (right-mover, left-mover) pair, resolve the collision with the same size rules and consume both slots. Survivors go into a fresh array. One sweep is never enough: the survivor of a pair can become adjacent to a defender further left, forming a brand-new collision that only the next sweep sees. Keep sweeping until a full pass changes nothing.

class Solution:
    def asteroidCollision(self, asteroids: list[int]) -> list[int]:
        changed = True
        while changed:
            changed = False
            nxt = []
            i = 0
            while i < len(asteroids):
                # A colliding pair is always "right-mover, then left-mover".
                if (
                    i + 1 < len(asteroids)
                    and asteroids[i] > 0
                    and asteroids[i + 1] < 0
                ):
                    left, right = asteroids[i], asteroids[i + 1]
                    if left == -right:        # equal sizes: both explode
                        i += 2
                    elif left > -right:       # left survives: keep it
                        nxt.append(left)
                        i += 2
                    else:                     # right survives: keep it
                        nxt.append(right)
                        i += 2
                    changed = True
                else:
                    nxt.append(asteroids[i])
                    i += 1
            asteroids = nxt
        return asteroids

Why it is quadratic: each sweep is O(n) work, but collisions can chain across sweeps. In the worst case a single big left-mover eats the right-movers one at a time — e.g. [10, 9, ..., 1, -100] advances the -100 one slot left per sweep — so the loop can run O(n) times for a total of O(n²). Rebuilding the array every pass also pays O(n) space per sweep.

Scan the array once. A right-mover cannot be hit from behind and cannot catch anything ahead, so push it and move on. A left-mover immediately goes to work, and the work is the whole algorithm: while the stack top is a weaker right-mover, pop it (it explodes) and keep resolving; if the top is equal, pop it and the incoming dies in the same round; if the top is stronger, the incoming explodes; and if the incoming outlasts the entire stack, push it — it becomes inert, since no later asteroid can ever catch a finished left-mover. Whatever remains in the stack, bottom to top, is the answer.

class Solution:
    def asteroidCollision(self, asteroids: list[int]) -> list[int]:
        stack = []
        for a in asteroids:
            # Only a left-mover meeting a right-mover can collide.
            while stack and stack[-1] > 0 and a < 0:
                if stack[-1] == -a:      # equal sizes: both explode
                    stack.pop()
                    a = 0
                elif stack[-1] < -a:     # top is smaller: top explodes, keep resolving
                    stack.pop()
                else:                    # top is bigger: incoming explodes
                    a = 0
            if a != 0:
                stack.append(a)
        return stack

Trace the file example, asteroids = [10, 2, -5] — the two-round cascade that shows why the while loop exists:

Then asteroids = [8, -8] — the equal-size branch, where one round destroys both fighters:

Why it is linear: every asteroid is pushed at most once and popped at most once — the cascade of pops is paid for by the elements it destroys — so the amortized work per asteroid is O(1), giving O(n) time overall. The stack is the output holder, so worst-case space is O(n) (e.g. every asteroid moving right). The survivors keep their original left-to-right order, so the stack is the answer as-is.