Asteroid Collision

Problem

You are given a row of asteroids as an integer array. Each value’s absolute size is the asteroid’s size, and its sign is its direction: positive moves right, negative moves left. All asteroids move at the same speed.

Two asteroids collide only when a right-mover is ahead of (to the left of) a left-mover — they drift toward each other. On collision the smaller one explodes; if they are the same size, both explode. Asteroids moving in the same direction never meet. Resolve all collisions and return the surviving asteroids, in order.

Examples

• [5, 10, -5] → [5, 10] — 10 and -5 collide, -5 explodes; -5 never reaches 5.
• [8, -8] → [] — equal sizes, both explode.
• [10, 2, -5] → [10] — -5 destroys 2, then loses to 10.
• [-2, -1, 1, 2] → [-2, -1, 1, 2] — left-movers on the left and right-movers on the right drift apart; no collision ever happens.

Constraints

• 2 <= asteroids.length <= 10^4
• -1000 <= asteroids[i] <= 1000, and asteroids[i] != 0

With n up to 10^4, a re-scan-after-every-collision simulation (O(n^2)) is the naive bar; the expected solution is a single O(n) pass.

Think about it first

TL;DR

Left-to-right pass with a stack of survivors; each incoming left-mover fights the positive stack tops — O(n) time, O(n) space.

Approach 1 — Brute force

Simulate literally: scan the current row for the first adjacent colliding pair (a positive immediately followed by a negative), resolve that collision, and restart the scan. Repeat until a full scan finds no collision.

class Solution:
    def asteroidCollision(self, asteroids: list[int]) -> list[int]:
        row = list(asteroids)
        while True:
            for i in range(len(row) - 1):
                if row[i] > 0 and row[i + 1] < 0:      # they drift together
                    left, right = row[i], row[i + 1]
                    if left == -right:
                        row[i : i + 2] = []            # both explode
                    elif left > -right:
                        row[i + 1 : i + 2] = []        # right one explodes
                    else:
                        row[i : i + 1] = []            # left one explodes
                    break
            else:
                return row

Complexity: O(n^2) time — up to n−1 collisions, each found by an O(n) rescan (plus O(n) list splices); O(n) space.

Why the constraints kill it: at n = 10^4, a chain like [1, 2, 3, ..., -10^9-ish] forces thousands of full rescans — ~10^8 operations for what one pass can do.

Approach 2 — Stack of survivors

The insight: processing left to right, a new right-mover can never hit anything already placed (everything to its left either moves left, away from it, or moves right ahead of it at the same speed). Only a new left-mover causes collisions, and it collides with the most recently placed surviving right-movers, nearest first — exactly the top of a stack. So each incoming negative asteroid fights the stack top while the top is positive, and either dies or keeps popping.

class Solution:
    def asteroidCollision(self, asteroids: list[int]) -> list[int]:
        stack: list[int] = []
        for a in asteroids:
            alive = True
            while alive and a < 0 and stack and stack[-1] > 0:
                top = stack[-1]
                if top < -a:          # top is smaller: it explodes, keep fighting
                    stack.pop()
                elif top == -a:       # equal: both explode
                    stack.pop()
                    alive = False
                else:                 # top is bigger: incoming explodes
                    alive = False
            if alive:
                stack.append(a)
        return stack

Walkthrough on [10, 2, -5]:

Result [10]. On [8, -8]: -8 meets top 8, equal, pop and die → []. On [-2, -1, 1, 2] no negative ever finds a positive top, so everything is pushed unchanged.

Complexity: O(n) time — each asteroid is pushed once and popped at most once, so the inner while is amortized O(1). O(n) space for the stack (which is also the answer).

Common pitfalls

• Treating every +/- pair as a collision: [-2, 1] never collides — the - is already left of the + and they separate. Only stack top > 0 and incoming < 0 fight.
• Forgetting the incoming asteroid can destroy several survivors: [1, 2, 3, -10] needs the while loop, not a single if.
• Mishandling the tie: on equal sizes you must both pop the top and kill the incoming asteroid — dropping only one of the two leaves a ghost survivor.
• Comparing signed values directly: compare stack[-1] with -a (sizes), not with a; sign mix-ups flip every battle.

Pattern takeaway

When items interact only with the most recent still-active items before them, keep survivors on a stack and let each new item “fight” the top in a pop-while loop. The amortized argument — every element pushed once, popped at most once — is the signature of these collision/absorption problems and returns in Daily Temperatures and monotonic-stack questions.