068. Asteroid Collision

Interview · Download this solution · All solutions and shared helpers

Problem

Asteroids lie in listed left-to-right order. A positive integer moves right, a negative integer moves left, and magnitude is size; zero is excluded. Equal-speed asteroids collide only when approaching. The smaller disappears; equal sizes both disappear. Return survivors in order.

Examples

Example 1

asteroid_collision([5, 10, -5])
=> [5, 10]

Ten destroys the smaller incoming asteroid.

Example 2

asteroid_collision([8, -8])
=> []

Equal approaching sizes both disappear.

Example 3

asteroid_collision([-2, -1, 1, 2])
=> [-2, -1, 1, 2]

These asteroids do not approach across a positive-negative boundary.

Reveal the worked solution and reasoning

Why this mechanism works

Only a right-moving stack top and a new left-moving asteroid can approach each other. A large incoming asteroid may destroy several earlier candidates, so resolve in a loop. Other sign combinations move apart or in parallel and cannot collide.

State and boundaries

stack is the fully resolved survivor sequence of the consumed prefix. alive indicates whether the incoming asteroid still exists.

Protocol

While incoming is left-moving and top is right-moving, compare sizes.
Pop a smaller top and continue.
Destroy both on equality.
Destroy incoming when top is larger.
Append incoming only if it survives.

Visualization

[10,2] incoming -5
2 disappears -> compare 10 with -5
-5 disappears -> survivor [10]

Python implementation

def asteroid_collision(asteroids):
    stack = []
    for asteroid in asteroids:
        alive = True
        while alive and asteroid < 0 and stack and stack[-1] > 0:
            if stack[-1] < -asteroid:
                stack.pop()
            elif stack[-1] == -asteroid:
                stack.pop()
                alive = False
            else:
                alive = False
        if alive:
            stack.append(asteroid)
    return stack

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

asteroid_collision([5, 10, -5])

L2 asteroid_collision: stack = []
asteroids=[5, 10, -5]; stack=[]

L3 asteroid_collision: for asteroid in asteroids:
asteroids=[5, 10, -5]; stack=[]; asteroid=5

L4 asteroid_collision: alive = True
asteroids=[5, 10, -5]; stack=[]; asteroid=5; alive=True

L14 asteroid_collision: stack.append(asteroid)
asteroids=[5, 10, -5]; stack=[5]; asteroid=5; alive=True

L3 asteroid_collision: for asteroid in asteroids:
asteroids=[5, 10, -5]; stack=[5]; asteroid=10; alive=True

L14 asteroid_collision: stack.append(asteroid)
asteroids=[5, 10, -5]; stack=[5, 10]; asteroid=10; alive=True

L3 asteroid_collision: for asteroid in asteroids:
asteroids=[5, 10, -5]; stack=[5, 10]; asteroid=-5; alive=True

L12 asteroid_collision: alive = False
asteroids=[5, 10, -5]; stack=[5, 10]; asteroid=-5; alive=False

Result: [5, 10]. Ten destroys the smaller incoming asteroid.

asteroid_collision([8, -8])

L2 asteroid_collision: stack = []
asteroids=[8, -8]; stack=[]

L3 asteroid_collision: for asteroid in asteroids:
asteroids=[8, -8]; stack=[]; asteroid=8

L4 asteroid_collision: alive = True
asteroids=[8, -8]; stack=[]; asteroid=8; alive=True

L14 asteroid_collision: stack.append(asteroid)
asteroids=[8, -8]; stack=[8]; asteroid=8; alive=True

L3 asteroid_collision: for asteroid in asteroids:
asteroids=[8, -8]; stack=[8]; asteroid=-8; alive=True

L9 asteroid_collision: stack.pop()
asteroids=[8, -8]; stack=[]; asteroid=-8; alive=True

L10 asteroid_collision: alive = False
asteroids=[8, -8]; stack=[]; asteroid=-8; alive=False

Result: []. Equal approaching sizes both disappear.

Why the solution is correct

The previously resolved prefix has no internal future collision. Any new collision must involve the incoming asteroid and the nearest survivor to its left. Resolving that pair either finishes the incoming asteroid or exposes the next possible pair, covering every collision in order.

Time and space

O(n) time and O(n) space; each asteroid enters and leaves the stack at most once.

Common mistakes

Treating every opposite-sign pair as colliding wrongly cancels [-2,1], which moves apart. A single comparison misses chain collisions.

Reasoning card

State: stack is the fully resolved survivor sequence of the consumed prefix. alive indicates whether the incoming asteroid still exists.

Invariant: Stack is the stable outcome of the processed prefix.

Decision to rehearse: Only a positive stack top and negative incoming asteroid can collide.

Finish: Append incoming only if it survives

Transfer exercise

Explain why different speeds would invalidate this stack-only event ordering and require time-aware collision reasoning.