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.

def asteroidCollision(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 run of positives followed by one larger negative — like [1, 1, ..., 1, -1000] — forces a full rescan after every collision, roughly 10^8 operations for what a single pass does in 10^4.

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) 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. That is 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.

Each incoming asteroid resolves through this decision:

flowchart TD
    A[Incoming asteroid a] --> B{a < 0 and stack top > 0?}
    B -->|no| P[Push a onto stack]
    B -->|yes| C{Compare top size vs -a}
    C -->|top smaller| D[Pop top, keep fighting]
    D --> B
    C -->|equal size| E[Pop top, a explodes]
    C -->|top bigger| F[a explodes]

def asteroidCollision(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.